You are viewing a single comment's thread. Return to all comments →
Can anyone help me to optimize this solution? I was able to come up with the recurrence relation and memoized it. But still getting TLE :(
TC: O(n * sqrt(n))
static int downToZeroHelper(int n, int[] dp) { if(n == 0) return 0; if(dp[n] != 0) return dp[n]; int min = Integer.MAX_VALUE; for(int i = 2; i * i <= n; i++) { if(n % i == 0) min = Math.min(min, 1 + downToZeroHelper(n / i, dp)); } return dp[n] = Math.min(min, 1 + downToZeroHelper(n - 1, dp)); } public static int downToZero(int n) { int dp[] = new int[n + 1]; return downToZeroHelper(n, dp); }
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
Can anyone help me to optimize this solution? I was able to come up with the recurrence relation and memoized it. But still getting TLE :(
TC: O(n * sqrt(n))