HackerRank K Factorization problem solution

In this HackerRank K Factorization problem solution At the time when Pythagoreanism was prevalent, people were also focused on different ways to factorize a number. In one class, Pythagoras asked his disciples to solve one such problem, Reverse Factorization. They were given a set of integer, A = {a1, a2,…, ak}, and an integer N. They need to find a way to reach N, starting from 1, and at each step multiplying the current value by any element of A. But soon they realized that there may exist more than one way to reach N. So they decided to find a way in which the number of states is least. All of a sudden they started on this new problem. People solved it and then started shouting their answer. CRAP!!!. There still exist multiple answers. So finally after much consideration, they settled on the lexicographically smallest series among those solutions which contains the least number of states.

Problem solution in Python.

def solve_greedy(numbers, target):
    numbers.sort(reverse=True)
    r = target
    res = [target]

    i = 0
    while i < len(numbers):
        if r % numbers[i] == 0:
            r //= numbers[i]
            res.append(r)
            
            if r == 1:
                return reversed(res)

            continue
        i += 1

    return [-1]

n = int(input().split()[0])
nums = list(map(int, input().split()))

print(*solve_greedy(nums, n))

Problem solution in Java.

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Solution {

    private static final Map<Integer, List<Integer>> cache = new HashMap<>();
    private static final List<Integer> one = Collections.singletonList(1);
    
    private static List<Integer> findBest(final int number, final Set<Integer> divisors) {
        if (number == 1)
            return one;
        if (cache.containsKey(number))
            return cache.get(number);
        List<Integer> best = null;
        for (final int divisor : divisors) {
            if (number % divisor == 0) {
                best = bestOf2(best, findBest(number / divisor, divisors));
            }
        }
        if (best == null)
            return null;
        best = new ArrayList<>(best);
        best.add(number);
        cache.put(number, best);
        return best;
    }
    
    private static List<Integer> bestOf2(final List<Integer> list1, final List<Integer> list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        if (list1.size() < list2.size())
            return list1;
        if (list2.size() < list1.size())
            return list2;
        for (int i = 0; i < list1.size(); i++) {
            final int x1 = list1.get(i);
            final int x2 = list2.get(i);
            if (x1 < x2)
                return list1;
            if (x2 < x1)
                return list2;
        }
        return list1;
    }
    
    public static void main(String[] args) {
        final Scanner scan = new Scanner(System.in);
        final int number = scan.nextInt();
        final int nDivisors = scan.nextInt();
        final Set<Integer> divisors = 
            IntStream
            .generate(() -> scan.nextInt())
            .limit(nDivisors)
            .boxed()
            .collect(Collectors.toSet());
        final List<Integer> solution = findBest(number, divisors);
        if (solution == null)
            System.out.println(-1);
        else
            solution.stream().forEach(el -> System.out.print(el + " "));
    }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int N, K, arr[25];
unordered_map<ll,int> jump[25];

int solve(int n, ll x){
    if(x==N) return 0;
    if(n==K || x>N) return 2e9;
    jump[n][x] = n;
    int ans = 1+solve(n, x*arr[n]);
    int val = solve(n+1, x);
    if(val<ans){
        ans = val;
        jump[n][x] = n+1;
    }
    return ans;
}

int main() {
    scanf("%d%d", &N, &K);
    for(int i=0; i<K; ++i) scanf("%d", &arr[i]);
    sort(arr, arr+K);
    int ans = solve(0, 1);
    if(ans>=2e9) printf("-1");
    else{
        int val = 1;
        int ind = 0;
        printf("1");
        while(true){
            int n = jump[ind][val];
            if(n==ind){
                val *= arr[ind];
                printf(" %d", val);
            }
            ind = n;
            if(val==N) break;
        }
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void recursion(int ,int ,int *,int *,int ,long long int);
int q1[10000]={},st=10000;
int main() {
    int n,k,i,arr[20]={},j,temp,ans[20]={};
    scanf("%d",&n);
    scanf("%d",&k);
    for(i=0,j=0;i<k;i++){
        scanf("%d",&temp);

        if(n%temp==0 && temp!=1)
            arr[j]=temp,j++;

        }
        k=j;
    for(i=0;i<k;i++)
        for(j=0;j<k-1;j++)
        if(arr[j]<arr[j+1])
    {temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}


            recursion(n,k,arr,ans,0,1);
   if(st==10000) printf("-1");
 else {temp=1;
printf("1 ");
            for(i=0;i<st;i++)
    printf("%d ",temp*=q1[i]);


    }

    return 0;
}
void recursion(int n,int k,int arr[],int ans[],int state,long long int var){

int p,t;

    if(n==var && st>state){
            int q;
            st=state;
            for(q=0;q<state;q++){
                q1[q]=ans[q];}
                return;}
if(n==var) return ;
if(k<=0 && var<n) return;
    if(k<0 || n<var) return;

            ans[state]=arr[k-1];
            recursion(n,k,arr,ans,state+1,var*arr[k-1]);
            recursion(n,k-1,arr,ans,state,var);

return;
}