Problem statement :
On a positive integer, you can perform any one of the following 3 steps.
Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1
eg:
I know the solution using dynamic programming and having a integer array. here is the code.
public int bottomup(int n) {
//here i am defining an integer array
//Exception is thrown here, if the n values is high.
public int[] bu = new int[n+1];
bu[0] = 0;
bu[1] = 0;
for(int i=2;i<=n;i++) {
int r = 1+bu[i-1];
if(i%2 == 0) r = Math.min(r,1+bu[i/2]);
if(i%3 == 0) r = Math.min(r,1+bu[i/3]);
bu[i] = r;
}
return bu[n];
}
But i want to solve this using less space.This solution throws OutofMemoryError in java if n=100000000.I don't want to increase my heap space.Does anyone has solution using less space?
Please note this problem cannot be solved using greedy algorthm.Using one while loop and check for divisible by 3 and divisible by 2 wont work.you have to use dynamic programming.please suggest if any has a solution using less space.
eg:
For n = 10 greedy algo is 10 /2 = 5 -1 = 4 /2 = 2 /2 = 1 which takes 4 steps.where as the solution should be 10-1 = 9 / 3 = 3 / 3 = 1, 3 steps.
I even tried topdown solution.
public int[] td = null;
public int topdown(int n) {
if(n <= 1) return 0;
int r = 1+topdown(n-1);
if(td[n] == 0) {
if(n%2 == 0) r = Math.min(r,1+topdown(n/2));
if(n%3 == 0) r = Math.min(r,1+topdown(n/3));
td[n] = r;
}
return td[n];
}
it is failing at n=10000.
One idea is that at any iteration you need the values only for r/3
to r
. So you can keep discarding 1/3rd
of the array.
I'm not familiar with Java
, but with C++
you can use a double ended queue (deque)
:
You keep adding to the deque from the back.
When i = 6
, you do not need bu[0]
and bu[1]
. So you pop out two elements from the front of the queue.
Random access [ ]
is supported with deque container.
EDIT: Also as suggested in the comments, you should change your datatype to a smaller sized one since the maximum number of steps shall be of the order of ( (log N) to base 2)
EDIT2: As Dukeling pointed out, it seems that in Java there is no ready-made well-suited implementation for deque that would not compromise on time complexity. You can think of implementing it in your own way as C++ does (I heard it is implemented as a vector of vectors with the size of inner vectors being small as compared to the total number of elements).
Recursive Solution For this problem
public static int countMinStepsTo1(int n){
if(n==1)
{
return 0;
}
int count1,count2=Integer.MAX_VALUE,count3=Integer.MAX_VALUE;
count1 = countMinStepsTo1(n-1);
if((n%2)==0)
{
count2=countMinStepsTo1(n/2);
}
if((n%3)==0)
{
count3=countMinStepsTo1(n/3);
}
return 1+Math.min(count1,Math.min(count2,count3));
}
DP Approch For this problem
public static int countstepsDP(int n)
{
int storage[] = new int[n+1];
storage[1]=0;
for(int i=2; i<=n;i++)
{
int min=storage[i-1];
if(i%3==0)
{
if(min>storage[i/3])
{
min=storage[i/3];
}
}
if(i%2==0)
{
if(min>storage[i/2])
{
min=storage[i/2];
}
}
storage[i]=1+min;
}
return storage[n];
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With