Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We can add do the following operations

a) add 1 to number

b) multiply number by 2

By using only a) and b) operations we can get any number from 0.

How much operations we need to do at least to get N?

share|improve this question
1  
Write $N$ in binary. –  Arthur Dec 28 '12 at 16:04

2 Answers 2

up vote 5 down vote accepted

Write $N\ge0$ in binary. Let $d_0(N)$ be the number of zeroes and $d_1(N)$ be the number of ones.

Claim: The minimal number of steps is $s(N):=d_0(N)+2d_1(N)-1$.

Proof: This is true for $N=0$, where $d_1(N)=0$, $d_0(N)=1$ and we need $0$ steps.

If $N=2k+1$ is odd, the last step must be addition of one. Hence to produce $N$ we must first produce $2k$, then add one. Note that $d_0(N)=d_0(2k)-1$, $d_1(N)=d_1(2k)+1$ and hence $s(N)=s(2k)+1$. Since $s(2k)$ is the minmal number of steps to produce $2k$, we conclude that $s(N)$ is the number of steps needed for $N$.

If $N\ge 2$ is even, we have two options: Produce $N-1$ and add one. Or produce $\frac N2$ and double. For the second method, we observe that $d_1(N)=d_1(\frac N2)$ and $d_0(N)=d_0(\frac N2)+1$ (this requires $N\ge2$), hence $s(N)=s(\frac N2)+1$. Thus we need to show that the path via $N-1$ cannot be better. If $N=2^r$ is a power of $2$ with $r\ge1$, note that $d_0(N)=r$, $d_1(N)=1$, $d_0(N-1)=0$, $d_1(N-1)=r$, hence $s(N)=r+1$, $s(N-1)=2r-1$. Thus $s(N)=s(N-1)+1$ if $r=1$ (i.e. we have a free choice to double or add in order to obtain $2$ from $1$), whereas $s(N)<s(N-1)+1$ for $r>1$ (i.e. the straightforward method via $\frac N2$ is strictly faster than the method via $N-1$). If $N=2^ru$ with $r\ge 1$ and $u>1$ odd, we have $d_0(N)=d_0(N-1)+r-1$, $d_1(N)=d_1(N-1)-r+1$, hence $s(N)=s(N-1)-r+1\le s(N-1)$. Therefore $s(N-1)+1>s(N)$, i.e. the method via $N-1$ is strictly slower than the method via $\frac N2$. $_\square$

share|improve this answer
    
+1 Hagen: It seems people are being a bit stingy with upvotes today! So I'm making a point of voting on (what I take to be) the best answers! –  amWhy Dec 28 '12 at 16:29

Think binary. If you write $N$ in binary notation, then multiplying by 2 simply shifts digits one space to the left and appends zero on the right. Thus, in at most two operations per binary digit of $N$, and working from the leftmost digits to the right, we could get from $0$ to $N$. That's at most $2 \lfloor \log_2 N \rfloor$ operations.

Here's an illustration with $N = 29$. In binary, $N = 11101$.

$$\begin{array}{ll} \textrm{start} & 0 \\ (+1) & 1 \\ (\times 2) & 10 \\ (+1) & 11 \\ (\times 2) & 110 \\ (+1) & 111 \\ (\times 2) & 1110 \\ (\times 2) & 11100 \\ (+1) & 11101 \\ \end{array}$$

share|improve this answer
    
but how to prove that it is optimal solution ? –  Ashot Dec 28 '12 at 16:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.