Better way to get shortest sequence

I want to get the shortest sequence to reach a number.

Rules:

• A[0] is always 1
• Either A[i] = A[i-1]*2 or A[i] = A[i-1]+1

For example, if my input number is 17, my output should be 6, because

A[0]=1, A[1]=2, A[2]=4, A[3]=8, A[4]=16, A[5]=17


Below is my code but it is not working properly for few inputs (ex. 15).

public static int GetMinimumSequence(int n)
{
if (n == 1)
return 1;

int count = 1;
int temp = 1;
for (int i = 2; i <= n; i++)
{
temp = temp * 2;
if (temp >= n)
{
temp = temp/2;
temp = temp + 1;
}
count++;
if(temp == n)
break;
}
return count;
}

-
I believe I've interpreted "minimum sequence" correctly as "shortest sequence". If not, please revert my edit and let me know. –  200_success Feb 5 at 6:53
This is the good old Hamming Weight Calculation. You will find dozens of different optimized implementations if you search for it on the net. –  Marcel Blanck Feb 5 at 7:40
I have updated my ideone ideone.com/OxKfHW to compare my answer with the OP code. They disagree (but are 'close'). -1 vote applied to question because the specification is ambiguous, and the code produces the 'wrong' result for power-of-2 input values (4, 8, 16, ...) –  rolfl Feb 5 at 12:59
"Below is my code but it is not working properly" What's it doing on Code Review? –  Ben Voigt Feb 6 at 18:10
@BenVoigt You are little late Ben. Yesterday I edited my post. Previously I thought it was a correct code and hence posted it here for better solution. But after few answers I found that my code was wrong for some scenarios. Hence I edited my post so that other users will not confused with my wrong code. –  Mukesh Rawat Feb 6 at 18:21

@CarySwoveland is on the right track. The original code and several other solutions so far get the wrong answer. For example, GetMinimumSequence(12) should not return 8, but rather 5, based on the optimal sequence 1, 2, 3, 6, 12.

One straightforward solution uses recursion:

public static int GetMinimumSequence(int n) {
if (n <= 0) {
throw new ArgumentOutOfRangeException();
} else if (n == 1) {
return 1;
} else if ((n % 2) == 1) {
return 1 + GetMinimumSequence(n - 1);
} else {
return 1 + Math.Min(GetMinimumSequence(n - 1),
GetMinimumSequence(n / 2));
}
}


Add memoization to that for better performance with larger inputs. (I'll leave that to you as an exercise.) In technical terms, this solution uses dynamic programming, since the greedy algorithm leads you astray.

-
Why are you using (n & 1) != 0 instead of n % 2 == 1, which I believe is more clear? –  svick Feb 5 at 11:05
+1 for finding bugs etc. Also I think I've corrected my answer with a solution that is more "straightforward" than yours is. –  ChrisW Feb 5 at 12:20
even best case with memoization will this be O(n) (going through the entire n-1 path), whereas if you always went down the optimal path then it would be O(log n) –  ratchet freak Feb 6 at 9:47
@ratchetfreak Your solution is vastly superior in practice. As ChrisW notes, the main redeeming factor of this naïve solution is that it is obviously correct by inspection. –  200_success Feb 6 at 9:54

1 point to remember:

the subsequence *2 +1 +1 can be simplified to +1 *2 (because n*2+2 is the same as (n+1)*2)

this means you can work backwards, odd numbers need a *2 +1 at the end of the sequence and even numbers get just a *2

count=1;
while(n>1){
if(n%2==0) count++;
else count+=2;
n/=2;//integer on positive number divide rounds down
}


given the optimization there is a sequence of +1 *2 (+1) *2 (+1) *2 (+1) *2 (+1) *2... which happens to coincide exactly with the binary representation of the number (a +1 means a 1 on that place while no +1 means a 0 on that place)

there are bit-hacking solutions to find both the number of bits set and the highest set bit, add them together and you will find the solution in constant time:

count = log2(n)+bitcount(n);


with log2 being:

int log2(int v){
int r; // result of log2(v) will go here
int shift;

r =     (v > 0xFFFF)?1 << 4:0; v >>= r;
shift = (v > 0xFF  )?1 << 3:0; v >>= shift; r |= shift;
shift = (v > 0xF   )?1 << 2:0; v >>= shift; r |= shift;
shift = (v > 0x3   )?1 << 1:0; v >>= shift; r |= shift;
r |= (v >> 1);
return r;
}


and bitcount being:

int bitcount(int v){
int c; // store the total here

c = v - ((v >> 1) & 0x55555555);
c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
c = ((c >> 4) + c) & 0x0F0F0F0F;
c = ((c >> 8) + c) & 0x00FF00FF;
c = ((c >> 16) + c) & 0x0000FFFF;
return c;
}


source of log2 and bitcount

-

My version of your code (other versions are a bit better; my version is more closely based on yours):

public static int GetMinimumSequence(int n)
{
if (n <= 0)
throw new ArgumentOutOfRangeException(); // or should return 0 when n == 0?

if (n == 1)
return 1;

int a = 1; // you call this 'temp', I call it 'a' to match the problem description
for (int i = 2; true; i++)
{
// can we afford to multiply by 2?
if (a*2 <= n)
a *= 2; // yes so multiply by 2.
else
// have we arrived at the correct result?
if (a == n)
return i;
}
}


A bug in your version is:

• Your if (temp >= n) is wrong; you want if (temp > n) instead (for example to get the right result when n is 16).

You don't need (and shouldn't have) i <= n as a condition in your for loop. The correct condition (the only condition in which you should return) is if(temp == n).

Instead of having a separate count, you can return i from inside the loop (as my example shows).

200_success' answer points out that we're using the wrong algorithm. He shows a recursive solution which looks correct.

I thought of a simpler algorithm as follows, which counts backwards.

public static int GetMinimumSequence(int n)
{
if (n <= 0)
throw new ArgumentOutOfRangeException();

for (int i = 1; ; ++i)
{
if (n == 1)
return i;
if ((n % 2) == 0)
n /= 2;
else
n -= 1;
}
}


Note:

• My algorithm is simpler than 200_success's
• 200_success's is more obviously correct by inspection
• I therefore test my algorithm against 200_success to demonstrate whether mine is correct
• I also tested against ratchetfreak's answer and found two small off-by-one bugs in that implementation, which I correct in the version below.

It's surprising how buggy most of the first implementations were. So another criticism of the code in the OP is that you didn't sufficiently test your implementation.

using System;

namespace GetMinimumSequence
{
class Program
{
static void Main(string[] args)
{
for (int i = 1; i <= 100; ++i)
{
int a = test_ChrisW(i);
int b = test_200_success(i);
if (a != b)
throw new ApplicationException(string.Format("Mismatch at {0}: {1} versus {2}", i, a, b));
}
for (int i = 1; i <= 100; ++i)
{
int a = test_ChrisW(i);
int b = test_ratchetfreak(i);
if (a != b)
throw new ApplicationException(string.Format("Mismatch at {0}: {1} versus {2}", i, a, b));
}
for (int i = 1; i <= 100; ++i)
{
Console.Write(@"Input " + i + " output " + test_ChrisW(i) + "\n");
}
}

public static int test_ChrisW(int n)
{
if (n <= 0)
throw new ArgumentOutOfRangeException();

for (int i = 1; ; ++i)
{
if (n == 1)
return i;
if ((n % 2) == 0)
n /= 2;
else
n -= 1;
}
}

public static int test_ratchetfreak(int n)
{
if (n <= 0)
throw new ArgumentOutOfRangeException();

int count = 1; //not count == 0
while (n > 1) // not while (n > 0)
{
if (n % 2 == 0) count++;
else count += 2;
n /= 2;
}
return count;
}

public static int test_200_success(int n)
{
if (n <= 0)
{
throw new ArgumentOutOfRangeException();
}
else if (n == 1)
{
return 1;
}
else if ((n % 2) == 1)
{
return 1 + test_200_success(n - 1);
}
else
{
return 1 + Math.Min(test_200_success(n - 1),
test_200_success(n / 2));
}
}
}
}

-

This question, in general, has proven to be problematic. Depending on which reference was used to 'understand' what the basic requirement is, there are two possible solutions.

In my first answer, I misread the spec. In my second version of the answer, I based the required logic on the actual code that MxR posted and claimed to 'work'.

Subsequently, the post has been 'clarified' and the real requirements have been identified as being different to my original understanding, and different to the OP's original 'working' code.

I have identified ways to solve this problem now in all three versions of the 'spec'.

Version 1: (my misread of the original spec)

.... no point in including it

Version 2:

This version is my second answer, based on the code example the OP included:

Below is my code which is working fine.

public static int GetMinimumSequence(int n)
{
if (n == 1)
return 1;

int count = 1;
int temp = 1;
for (int i = 2; i <= n; i++)
{
temp = temp * 2;
if (temp >= n)
{
temp = temp/2;
temp = temp + 1;
}
count++;
if(temp == n)
break;
}
return count;
}


The following answer is the one I proposed as a "Better Way".

This is actually a simple (if you know logs) mathematical problem:

What you want is the number of powers-of-two that are smaller than your input value, and then you want to 'step' forward until you get to your value.

So, for example, with 17, the previous power-of-2 is 16 (which is 24). You then step forward 1 to get to 17.

The math for this is:

• calculate the previous power-of-2's exponent.
• calculate the difference between that power-of-2, and our input value.

The integer-part of the Log2 of the value is the exponent of the previous power of 2.

This results in:

public static int GetMinimumSequence(int n)
{
int prevexponent = (int)Math.Log(n, 2);
// ( 1 << prevexponent) is same as (int)Math.Pow(2, prevexponent) but faster
return 1 + prevexponent + n - (1 << prevexponent);
}


Version 3

A number of other answers have also been given that calculate the 'shortest distance' using the details of the OP's rules using the 'alternative' interpretation of the specification.

• A[0] is always 1
• Either A[i] = A[i-1]*2 or A[i] = A[i-1]+1

what is the smallest number of steps (i + 1) that can get you to a target value?

The answers presented so far use recursion:

or some other loops:

or an O(1) implementation

From what I can tell, the above answers are the only ones that produce the results according to this version of the spec.

I dislike both ChrisW and 200_success's answers because:

• The recursive approach is speculative, and does too much work to get to the answer.
• The loop approach does not make the mathematical logic clear.

A better approach is the following:

public static int GetMinimumSequenceRL(int n)
{
int cnt = 0;
while (n > 0) {
cnt++;
n = (n % 2 == 0)  ?  (n / 2)  :  (n - 1);
}
return cnt;
}


This approach works backwards from the target. If the value is odd, it subtracts one, if it is even, it halves it.

Each of these operations is a 'step', and it counts how many steps to get back to 0.

Mathematically, this is guaranteed to bring you back on the shortest possible path, and it works without having to speculate down unused paths.

ChrisW's solution is far better than the recursive approach, and it uses the same basic mathematical approach that I propose, but the for (i....) loop gives the code a misleading 'flavour', that it is looping through something finite... yet the code's only exit point is 'return' inside that loop.

BUT THE BEST solution is the one from Ratchet Freak, which is the most elegant.

It does the bitcount (number of odd values) and the log2 which is the number of doubles.

Unfortunately, he does not make that logic very clear..... but, if it were me, I would accept that answer as the best solution.

In java, by the way, this solution is a 1-liner:

public int getShortestSequence(int n) {
return Integer.bitCount(n) + Integer.highestOneBit(n) - 1;
}


Conclusion

• The best way to get the sequence is through the smart application of mathematics, not through a trial-and-error recursive approach
• When posting to CodeReview, it is always best to put full specifications in place
• When answering on CodeReview, it is best to clarify any ambiguity before you commit.

I have updated the ideone to include the OP solution, my version 2 solution, and then ChrisW's, 200_success, and my version 3.

-
I think this gives the correct result for n=16 and 17, but not for 18. –  ChrisW Feb 5 at 3:12
@ChrisW - included link to an ideone –  rolfl Feb 5 at 3:19
Yes; I still think it's wrong: to get to 18 you need to double a few times and then add 1 twice; or add 1 three times to get to 19. Math/Ceiling isn't enough except when the desired result is (2^n) or (2^n + 1). –  ChrisW Feb 5 at 3:22
Ahhh.... I believe you are right .... let me fix that for me. –  rolfl Feb 5 at 3:22

This is not a solution, but is what I believe are the shortest paths for numbers up to 30. Each row contains n, the smallest number of steps from 0 to n and the associated path. I thought it might be useful to post this, first to have it checked by readers, then to help others check their code. I coded this in Ruby, which is why I've not posted a solution.

   [[2,  2, [0, 1, 2]],
[3,  3, [0, 1, 2, 3]],
[4,  3, [0, 1, 2, 4]],
[5,  4, [0, 1, 2, 4, 5]],
[6,  4, [0, 1, 2, 3, 6]],
[7,  5, [0, 1, 2, 3, 6, 7]],
[8,  4, [0, 1, 2, 4, 8]],
[9,  5, [0, 1, 2, 4, 8, 9]],
[10, 5, [0, 1, 2, 4, 5, 10]],
[11, 6, [0, 1, 2, 4, 5, 10, 11]],
[12, 5, [0, 1, 2, 3, 6, 12]],
[13, 6, [0, 1, 2, 3, 6, 12, 13]],
[14, 6, [0, 1, 2, 3, 6, 7, 14]],
[15, 7, [0, 1, 2, 3, 6, 7, 14, 15]],
[16, 5, [0, 1, 2, 4, 8, 16]],
[17, 6, [0, 1, 2, 4, 8, 16, 17]],
[18, 6, [0, 1, 2, 4, 8, 9, 18]],
[19, 7, [0, 1, 2, 4, 8, 9, 18, 19]],
[20, 6, [0, 1, 2, 4, 5, 10, 20]],
[21, 7, [0, 1, 2, 4, 5, 10, 20, 21]],
[22, 7, [0, 1, 2, 4, 5, 10, 11, 22]],
[23, 8, [0, 1, 2, 4, 5, 10, 11, 22, 23]],
[24, 6, [0, 1, 2, 3, 6, 12, 24]],
[25, 7, [0, 1, 2, 3, 6, 12, 24, 25]],
[26, 7, [0, 1, 2, 3, 6, 12, 13, 26]],
[27, 8, [0, 1, 2, 3, 6, 12, 13, 26, 27]],
[28, 7, [0, 1, 2, 3, 6, 7, 14, 28]],
[29, 8, [0, 1, 2, 3, 6, 7, 14, 28, 29]],
[30, 8, [0, 1, 2, 3, 6, 7, 14, 15, 30]]]


Edit: I decided to post my Ruby code, just to show the approach I used. If you don't know Ruby, think of it as pseudo-code.

def min_seq(n)
return [0, []] if n.zero?
return [1, [0,1]] if n == 1
seq = { 0 => {d: 0, p: nil}, 1 => {d: 1, p: 0} }
(2..n).each do |i|
j = i-1
j = i/2 if ( i.even? && (seq[i/2][:d] < seq[i-1][:d]) )
seq.merge! ( { i => { d: seq[j][:d]+1, p: j } } )
end
path = [n]
loop do
path << (n = seq[n][:p])
break if n.zero?
end
path.reverse!
[path.size-1, path]
end


n is the given positive integer. For any m <= n, the hash seq contains keys 0, 1,...,m, where seq[k] = { :d => x, :p => i }, 0 <= k <= m, x being the minimum number of steps from 0 to k and i being the previous number on the shortest path. seq initially has keys 0 and 1, then 2 is added, then 3, and so on up to n, at which point the shortest path to n is available. The shortest path is determined in the code that precedes path = [n]; the remaining statements merely extract it from seq.

-
This is a lookup table for the array that he used to explain what he wants. But actually he wants to count the bits in an integer. Your hard drive would be full with such a list xD –  Marcel Blanck Feb 5 at 7:42

Improved the speed of the recursive solution. It stops now within a reasonable time for numbers larger than 1000.

static Dictionary<int,int> cache = new Dictionary<int,int>();

public static int GetMinimumSequence(int n) {
if (n <= 0) {
throw new ArgumentOutOfRangeException();
} else if (n == 1) {
return 1;
} else if (cache.ContainsKey(n)) {
return cache[n];
}

int r;
if ((n % 2) == 1) {
r = 1 + GetMinimumSequence(n - 1);
} else {
r = 1 + Math.Min(GetMinimumSequence(n - 1),
GetMinimumSequence(n / 2));
}
return r;
}

-

public static int GetMinimunSequence(int n)
{
int count = 1;
int current = 1;

while(current * 2 <= n){
current *=2;
count++;
}

while(current + 1 <= n) {
current++;
count++;
}

return count;
}

-