Question

Consider a non-zero positive decimal number, innum , an integer inbase greater than 1
and print outnum, the maximum number of consecutive set of zeroes after converting
innum to its inbase notation.
2
Print - 1 if there exists no zero after conversion of innum.
Input format:
w
113
First line contains innum
Second line contains inbase
Read the input from the standard input stream
Output format:
Print outnum or -1 to the standard output stream
​

Answer 1

Answer:

Consider a non-zero positive decimal number, innum , an integer inbase greater than 1

and print outnum, the maximum number of consecutive set of zeroes after converting

innum to its inbase notation.

2

Print - 1 if there exists no zero after conversion of innum.

Input format:

w

113

First line contains innum

Second line contains inbase

Read the input from the standard input stream

Output format:

Print outnum or -1 to the standard output stream

Answer 2

Answer:

A naive approach would be to simply loop over the bits and keep track of the number of consecutive set bits as well as the maximum value obtained.

Explanation:

We must convert it to binary (base-2) representation before finding and printing the result in this method.

Using Bit Magic: The principle is that by AND a bit sequence with a shifted version of itself, we can effectively remove the trailing 1 from every series of consecutive 1s.

  11101111   (x)

   & 11011110   (x << 1)

   ----------

     11001110   (x & (x << 1))

       ^    ^

       |    |

  trailing 1 removed

In binary representation of x, the operation x = (x & (x & 1)) lowers the length of every sequence of 1s by one. If we repeat this method indefinitely, we will arrive at x = 0. The length of the longest consecutive series of 1s determines the number of iterations required to achieve zero.