Hi. I am trying to solve this problem.
For convenience, I have replicated the problem statement below:
Given a list of N integers (non-distinct) where and each integer , sort the integers based on the lexicographical order of their prime factorization.
Example (the first number is N):
5
2 3 4 5 6
Expected Output:
2
4
6
3
5
Explanation:
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
Time limit is 2s and memory limit is 32MB.
My attempt:
I used a fast factorization method to factor each integer into its prime factors and store them into a 2D matrix, M. M[i][j] represents the jth prime factor of the ith integer in the list such that M[i][j] ≤ M[i][j + 1].
Now, I use a custom sort method to sort the list. Let's say we want to compare integers at position u and v in the list.The sort function will compare M[u] and M[v] using lexicographical comparison.
My code.
This method is correct but it will get MLE (not TLE surprisingly). I tried asking this problem on stackoverflow but could not obtain a satisfactory answer. Could someone please advise me on a better way to solve this problem?
p.s. not sure if this info would be helpful — this problem is tagged with dfs in the source.