327 views

2 Answers

1 votes
1 votes

Let's bring our entire focus to the expression on line no. 8 (parenthesizing for comprehension).

$$x = (x + 1) - (N\%2)$$

This expression gives us an initial idea of the way $x$ increments. For all even values of $N$, $x$ increments by one. And for all odd values of $N$, $x$ will continue to possess its current value. The next line tells us that the value of $N$ decreases by the factor of $2$ in each iteration. This fact gives us the clue that binary equivalent of $N$ can be helpful in finding the answer.

Now, if we try to reinterpret the expression on line no. 8 in terms of binary equivalent of $N$ we get something interesting. For every zero in binary equivalent of $N$, the value of $x$ increments by one. And for every one in binary equivalent, $x$ retains its value.Therefore, for $x$ to be equal to $5$ we need exactly five zeroes in binary equivalent of $N$.

The value of $N$ cannot be $(00000)_2 = (0)_{10}$, because of while loop termination condition. It can also not be equal to $(000001)_2=(1)_{10}$ or something of this sort because the preceding zeroes will not let the loop continue for as long as we want. Thus the minimum value of $N$ for which we can get $x=5$ is

$$(100000)_2 = (32)_{10}$$

For the next two minimum values of $N$ for which $x=5$, we can add more ones to its binary equivalent (because that will not increase the value of $x$). Since we need next minimum value, we add an extra one after the least significant bit in binary equivalent of $32$, to get

$$(1000001)_2 = (65)_{10}$$

For the third minimum number, we can just shift $65$ towards left by one bit to get

$$(1000010)_2 = (66)_{10}$$

Note, we cannot add more zeroes to the binary equivalent of $N$ because that will increase the value of $x$.

Therefore the answer to this question is $163$


To check my answer, I modified the given program to list possible solution within the range of 10 to 70 (rough guess). Here is the source code, just for reference.

0 votes
0 votes
First for loop will run one time.

Second for loop will run 2N time and for each execution of second for loop while loop will run N time.

So the complexity is O(N2).