Problem
I want to get the shortest sequence to reach a number.
Rules:
A[0]is always 1- Either
A[i] = A[i-1]*2orA[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
The following code is not working properly for few inputs, such as 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;
}
Solution
@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.
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;
}
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.
- add them.
- add 1.
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); }
This answer was a decent answer, given the assumption it (incorrectly) made about the specification being provided by the ‘working code’.
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.
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
a += 1; // no so just add 1 instead
// 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 wantif (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 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.