Given number of test cases T and an integer N, you need to find four integers A,B,C,D , such that they're all factors of N(A|N,B|N,C|N,D|N), and N=A+B+C+D. Goal is to maximize A * B * C * D. If it's not possible to find such four factors simply return -1.
Input format for the problem is:
First line contains an integer T(1<=T<=40000), represents the number of test cases.
Each of the next T lines contains an integer N (1<=N<=40000, N^4 will not exceed 64 bit integer).
This question is on Hackerearth under recursion category, but i'm not able to understand the algorithm in the editorial( editorial link:- https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/practice-problems/algorithm/divide-number-a410603f/editorial/).
In the editorial it's been solved using unit fractions but i'm not able to understand the algorithm( I've provided the editorial below if you are not able to open the above link, I'm not able to understand the points marked with ***). Brute force solution results in TLE(Time Limit Exceeded). Please provide algorithm or pseudo-code using DFS or backtracking.
My brute force approach:- calculate the factors of a number 'n' in O(sqrt(n)) and store them in an array, then traverse the array to get A,B,C,D using four for loops. But for T(1<=T<=40000) test cases it gets TLE.
Editorial(If you are not able to open the above link):-
Consider the equation N = A+B+C+D , if we divide the equation by N , we get 1 = 1/A' + 1/B' + 1/C' + 1/D' , here A',B',C',D' are all intergers, because A,B,C,D are factors of N.
So the original problem is equal to divide 1 into four unit fractions.
We can enumerate the unit fractions from large to small.
*** If we need to divide X into Y unit fractions, and the last unit fraction is 1/Z, we can enumerate unit fractions between 1/Z and X/Y(because we are enumerating the largest remaining fraction), and recursively solve.
*** After find all solutions to 1 = 1/A' + 1/B' + 1/C' + 1/D' (about 20 solutions if the numbers are in order), we can enumerate them in each test case. If A',B',C',D' are all factors of N, we can use this solution to update the answer.
Time Complexity: O(T), where T is the number of Test cases.
*** If we need to divide X into Y unit fractions, and the last unit fraction is 1/Z, we can enumerate unit fractions between 1/Z and X/Y(because we are enumerating the largest remaining fraction), and recursively solve.
Answer: We are trying to find out all the combination from 1 = 1/A + 1/B + 1/C + 1/D. Initially, we have X=1 and Y=4, and we are enumerating A as the largest factor, which should be no less than X/Y = 1/4. Because this is the first element, there is no last fraction 1/Z. Suppose we chose A=3, so last fraction 1/Z is 1/A=1/3, and X=1-1/3=2/3, and Y=3. Now we shall choose 1/B from [X/Y, 1/Z] = [2/9, 1/3]. And do the same thing for the next steps.
*** After find all solutions to 1 = 1/A' + 1/B' + 1/C' + 1/D' (about 20 solutions if the numbers are in order), we can enumerate them in each test case. If A',B',C',D' are all factors of N, we can use this solution to update the answer.
Answer: Because 1/A should be no less than 1/4, so A could only be 2, 3, 4. If A==4, then A=B=C=D, only have one solution. If A==3, [X/Y, 1/Z] = [2/9, 1/3], so B could only be 3 or 4, if B ==4, then next round C should be 4 where [X/Y, 1/Z] = [5/24, 1/4]; if B=3, then C could be 4,5,6 because [X/Y, 1/Z]=[1/6,1/3]. If A==2, [X/Y, 1/Z] = [1/6, 1/2], B could be 3,4,5,6. You could do the rest calculation using the code, feel like we could cut off many search branches. (Ignore my enumeration order, you should start from A=2. )