We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I tried using Greedy approach and it passes all the tests (java)
publicstaticList<Integer>kFactorization(intn,List<Integer>nums){//List for storing the divisors of the numbersList<Integer>ansNums=newArrayList<>();//Sort the nums in reverse order for minimum no of steps for reaching the number nCollections.sort(nums,Collections.reverseOrder());//initialize the flag to truebooleanisDiv=true;//keep looping until we reached num from n to 1 and in each iteration number was divided.while(isDiv&&n>=1){isDiv=false;//set the flag to false to check if there was a divisorfor(intnum:nums){if(n%num==0){//if divisor foundansNums.add(num);n=n/num;isDiv=true;//set the flag true}}}Collections.sort(ansNums);//sort the list bcz we added it in reverse orderList<Integer>ans=newArrayList<>();if(ansNums.isEmpty()||n!=1){//if we didn't reach the number, return -1ans.add(-1);returnans;}else{ans.add(1);//else add initial 1 //Multiply the number with divisors and add to the final listfor(intnum:ansNums){ans.add(ans.get(ans.size()-1)*num);}returnans;}}
That's rather sloppy of them. The greedy algorithm fails on e.g. making 84 from [2, 3, 7, 12, 14], since the optimal factorization is 7*12 which you can't find if you start by selecting 14; you'd think they'd include some such tests.
K Factorization
You are viewing a single comment's thread. Return to all comments →
I tried using Greedy approach and it passes all the tests (java)
That's rather sloppy of them. The greedy algorithm fails on e.g. making 84 from [2, 3, 7, 12, 14], since the optimal factorization is 7*12 which you can't find if you start by selecting 14; you'd think they'd include some such tests.
Thanks, Alex! I almost missed this for my greedy python solution. Indeed very sloppy - this task needs new tests.