Author |
Topic: minimum steps of n to 1 (Read 987 times) |
|
bbskill
Newbie
Posts: 42
|
 |
minimum steps of n to 1
« on: Nov 5th, 2007, 6:24am » |
 Quote  Modify
|
assume the method int func(unsigned).
if n is even, then n is divided by 2.
if n is odd, then n is added by 1 or subtracted by 1.
end if n becomes 1.
This method return the minimum number of steps of translate the given n to 1.
for example:
7, the minimum number of steps to become 1 is 4.
7 --> 6 -->3 --> 2 -> 1
15,the minimum number of steps to become 1 is 5.
15 -> 16 ->8 -> 4 ->2 ->1.
Please implement the func(unsigned). Any sugestion? or better than o(logn) suloction.
Thanks.
|
| « Last Edit: Nov 5th, 2007, 6:27am by bbskill » |
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: minimum steps of n to 1
« Reply #1 on: Nov 5th, 2007, 7:23am » |
Quote Modify
|
Isn't it always better to subtract one? (For positive numbers, at least).
|
| « Last Edit: Nov 8th, 2007, 4:10pm by Grimbal » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: minimum steps of n to 1
« Reply #2 on: Nov 5th, 2007, 7:29am » |
Quote Modify
|
Clearly not. Consider the example provided of 15:
By always subtracting:
15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 (6 steps)
By adding on the first step:
15 -> 16 -> 8 -> 4 -> 2 -> 1 (5 steps)
My first-draft strategy would be to always choose the number with the higher multiplicity of 2.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: minimum steps of n to 1
« Reply #3 on: Nov 5th, 2007, 7:58am » |
Quote Modify
|
I see. I thought +1/-1 and divide were one step. Sorry.
Then I guess you should add or subtract to make a multiple of 4 and guarantee 2 divisions. Except when you reach 3, where you should do -1. I don't know if there are other exceptions.
|
|
IP Logged |
|
|
|
nitin_162
Newbie
Gender:
Posts: 33
|
|
Re: minimum steps of n to 1
« Reply #4 on: Nov 7th, 2007, 12:58am » |
Quote Modify
|
I think we can use bit manipulation stuff..
Right shift the number by 1 till the number becomes 1.
int count = 0;
int x = n;
while(x != 1){
x = x >>> 1;
count++;
}
This approach is pretty much similar to the 1st one but in case of the number being odd this transformation approach takes less steps.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: minimum steps of n to 1
« Reply #5 on: Nov 7th, 2007, 1:46am » |
Quote Modify
|
on Nov 7th, 2007, 12:58am, nitin_162 wrote:I think we can use bit manipulation stuff..
Right shift the number by 1 till the number becomes 1.
int count = 0;
int x = n;
while(x != 1){
x = x >>> 1;
count++;
}
This approach is pretty much similar to the 1st one but in case of the number being odd this transformation approach takes less steps.
|
|
This problem is not equivalent to finding the position of the highest order bit, which is what you seem to be doing (although the >>> is rather flummoxing)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
GowriKumar
Junior Member
 
Gender:
Posts: 55
|
|
Re: minimum steps of n to 1
« Reply #6 on: Nov 7th, 2007, 4:54am » |
Quote Modify
|
on Nov 7th, 2007, 1:46am, towr wrote:
(although the >>> is rather flummoxing) |
|
Probably it is unsigned shift right (from the Java world)??
Ofcourse, it doesn't seem to have any significance with the problem at hand.
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: minimum steps of n to 1
« Reply #7 on: Nov 7th, 2007, 5:04am » |
Quote Modify
|
on Nov 7th, 2007, 4:54am, gowrikumar wrote:| Probably it is unsigned shift right (from the Java world)?? |
|
Ah, I'm showing my ignorance of Java again 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: minimum steps of n to 1
« Reply #8 on: Nov 7th, 2007, 8:42am » |
Quote Modify
|
This problem is quite intersting. As a starting point, I wrote the following program to implement the
O(logn) solution:
Code:
#include <stdio.h>
#define NUM 30
unsigned int arr[NUM];
unsigned int min(unsigned int a, unsigned int b)
{
if(a<b)
return a;
return b;
}
unsigned int fun(unsigned int i)
{
if(i==2)
return 1;
if(i == 3)
return 2;
if(i&1)
{
return 1 + min(fun(i+1),fun(i-1));
}
else
return 1 + fun(i/2);
}
int main()
{
unsigned int i;
for(i=2;i<NUM;i++)
printf("%u : %u\n",i,fun(i));
return 0;
}
|
|
It still needs to be analyzed if there is a fixed pattern.
|
|
IP Logged |
www.gowrikumar.com
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: minimum steps of n to 1
« Reply #9 on: Nov 7th, 2007, 8:42am » |
Quote Modify
|
int quickest(int n)
{
if(n==3 || n==4)
return 2;
int steps=1;
if(n%2==0)
steps+=quickest(n/2);
else
steps+=min(quickest(n-1),quickest(n+1));
return steps;
}
|
|
IP Logged |
All signatures are false.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: minimum steps of n to 1
« Reply #10 on: Nov 7th, 2007, 10:07am » |
Quote Modify
|
on Nov 7th, 2007, 8:42am, gowrikumar wrote:This problem is quite intersting. As a starting point, I wrote the following program to implement the
O(logn) solution: |
|
It seems rather exponential in the number of bits, to be honest.. So for a starting number N it would be O(N).
You can't get O(log(n)) until you can avoid having to examine both choices for odd numbers.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dont.hurt.again
Newbie
Posts: 6
|
|
Re: minimum steps of n to 1
« Reply #11 on: Nov 8th, 2007, 12:40pm » |
Quote Modify
|
well i have an idea how solution might look like.
what we have to do here is to make no of 1`s in the binary format of that no to minimum.
lets say the no has last two bits as 1(3,7 etc)
add 1 to them.as adding 1 to them will lower no of 1`s in the no at least by 1 may be more than that.
in case no being 3 subtract 1.
well if there is no 0 at the second last digit then subtract it by 1.
I am not sure if this solution is optimal.
ex- 13=1101
it can be done as
13-12-6-3-2-1
11=1011
11-12-6-3-2-1
11-10-5-4-2-1
here add 1 or subtracting is not making any changes as no has 0 at 3rd lowest digit.
but let say no is 15=1111
15-16-8-4-2-1
15-14-7-8-4-2-1
a single step increased.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: minimum steps of n to 1
« Reply #12 on: Nov 8th, 2007, 4:14pm » |
Quote Modify
|
I came up with the following, assuming +/- aiming at a multiple of 4 is the shortest way.
int f (int n){
int s=0;
while( n>=4 ){
if( n%2==0 ) n = n>>1, s++;
else n = (n+1)>>2, s += 3;
}
return s+n-1;
}
|
|
IP Logged |
|
|
|
aditi
Newbie
Posts: 17
|
|
Re: minimum steps of n to 1
« Reply #13 on: Nov 12th, 2007, 4:53pm » |
Quote Modify
|
@bbskill
Can you post the O(logn) solution that you know??
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: minimum steps of n to 1
« Reply #14 on: Nov 13th, 2007, 5:08am » |
Quote Modify
|
There is a while(n>1) missing somewhere.
|
|
IP Logged |
|
|
|
bbskill
Newbie
Posts: 42
|
|
Re: minimum steps of n to 1
« Reply #15 on: Nov 13th, 2007, 5:30am » |
Quote Modify
|
on Nov 12th, 2007, 4:53pm, aditi wrote:@bbskill
Can you post the O(logn) solution that you know?? |
|
This is my strategy:
We could find the minimum steps is the sum of bit numbers of n and the number of bit 1 of n.
So, we could follow the following strategy:
Code:
int ff(int n) {
int s = 0;
while (n > 1) {
if (n%2 == 0) { // n ends with 0
n >>= 1;
} else if ((n & 0x3) == 1 || n == 3) { // n ends with 01 or n == 3
n -=1;
} else { // n ends with 11 except for 3.
n += 1;
}
s ++;
}
return s;
}
|
|
|
| « Last Edit: Nov 13th, 2007, 5:34am by bbskill » |
IP Logged |
|
|
|
aditi
Newbie
Posts: 17
|
|
Re: minimum steps of n to 1
« Reply #16 on: Nov 13th, 2007, 9:19am » |
Quote Modify
|
@bbskill
Thanks for the post.
However, your strategy will fail for n=7. It will add 1 to n because 7 in binary ends with 11. Thats is incorrect.
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: minimum steps of n to 1
« Reply #17 on: Nov 13th, 2007, 9:24am » |
Quote Modify
|
on Nov 13th, 2007, 9:19am, aditi wrote:@bbskill
Thanks for the post.
However, your strategy will fail for n=7. It will add 1 to n because 7 in binary ends with 11. Thats is incorrect. |
|
7 -> 6 -> 3 -> 2 -> 1
7 -> 8 -> 4 -> 2 -> 1
I don't see the problem.
|
|
IP Logged |
|
|
|
dont.hurt.again
Newbie
Posts: 6
|
|
Re: minimum steps of n to 1
« Reply #18 on: Nov 13th, 2007, 9:33pm » |
Quote Modify
|
on Nov 13th, 2007, 5:30am, bbskill wrote:
This is my strategy:
We could find the minimum steps is the sum of bit numbers of n and the number of bit 1 of n.
[/code] |
|
the step count u are saying here will be the upper bound. The exact soln may have less no of steps as in case of 15.
Though ur code will work perfectly.
the problem is that when u have 111 in the end adding 1 will change the no of one`s in the by more than 1.
111+1 = 1000 two changes.
|
|
IP Logged |
|
|
|
GowriKumar
Junior Member
Gender:
Posts: 55
|
|
Re: minimum steps of n to 1
« Reply #19 on: Nov 14th, 2007, 9:37pm » |
Quote Modify
|
on Nov 13th, 2007, 5:30am, bbskill wrote:
This is my strategy:
We could find the minimum steps is the sum of bit numbers of n and the number of bit 1 of n.
So, we could follow the following strategy:
Code:
int ff(int n) {
int s = 0;
while (n > 1) {
if (n%2 == 0) { // n ends with 0
n >>= 1;
} else if ((n & 0x3) == 1 || n == 3) { // n ends with 01 or n == 3
n -=1;
} else { // n ends with 11 except for 3.
n += 1;
}
s ++;
}
return s;
}
|
|
|
|
Wow!! that's cool solution. And here is my understanding/analysis of it:
If we examine the last two bits of the number:
00 - even
01 - odd
10 - even
11 - odd
If the number is even, we will just divide it by two.
If the number is odd, the possibilites as listed above are:
01 and 11
We need to ensure that the addition/subtraction would result in maxiumum number of divisions by two.
Here is this case,
adding 1 to 11 makes it 00 (and a carry of 1 )
The resultant is divisble by 4 (hence 2 divisions)
and for the other
substracting 1 from 01 makes it 00
The resultatn agains is divisble by 4
Hence, the code would give the minimum number of steps required.
Regards,
Gowri Kumar
|
|
IP Logged |
www.gowrikumar.com
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: minimum steps of n to 1
« Reply #20 on: Nov 15th, 2007, 2:40am » |
Quote Modify
|
Once you know you have a multiple of 4, you might as well divide by 4 straight away and count 2 more steps. That is, except for n<2.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print