Given a number N. Find the minimum number of operations required to reach N starting from 0. You have 2 operations available:
- Double the number
- Add one to the number
Problem is to find minimum number of operations required to reach to N starting from 0. Operation allowed are only addition of 1 or multiplication by 2.
Obvious approach
Start from 1 , with minimum operations set to 1. Explore all possible options to reach N. With this approach, possible code would be:
int minOperations(int s, int N) {
if (s==N) return 0;
if (s==0) { s++; return 1 + minOperations(s, N); }
return 1+ Math.min(minOperations(s+1, N), minOperations(s*2, N));
}
This approach works. But as N grows, this leads to stackoverflow. Lets analyze what's happening here.
Ex:
For N=3
Iteration-1: s=0 -> s=1, min = 1
Iteration-2: s=1-> s=2, min = 2
-> s=2, min = 2
Iteration-3.a s=2-> s=3, min = 3
-> s=4, min = 3
Iteration-3.b s=2-> s=3, min = 3
-> s=4, min = 3
...
Here we see so many repetitive operations in a small data-set itself. These repetitive jobs eat up the stack and lead to overflow for larger N.
Memoization Approach
Next obvious choice is to introduce the Memoization, in which a memory is introduced to cache the already calculated value and not repeat the job.
int minOperations(int s, int N, Map<Integer, Integer> map) {
if (s==N) return 0;
if (map.containsKey(s)) return map.get(s);
if (s==0) { return 1 + (1, N); }
map.put(s, 1+ Math.min(minOperations(s+1, N), minOperations(s*2, N)));
return map.get(s);
}
This approach looks fine but is there a scope of improvement.