Skip to main content

Oracle

Oracle OA-9 2024

Problem Description

Given an integer, store its binary representation as a string or an array with digits indexed from 0 to length(bin) - 1. Reduce its binary representation to zero by using the following operations:

  1. Change the t-th binary digit only if the (i + 1)-th binary digit is 1 and all other binary digits from (i + 2) to the end are zeros.
  2. Change the rightmost digit without restriction.

What is the minimum number of operations required to complete this task?

Example:

For n = 4:

The binary representation of 4 is 100, so for the example, bin = [1, 0, 0].

100 -> 101 -> 111 -> 110 -> 010 -> 011 -> 001 -> 000

Stepping through the operations:

  • Use rule 2 to change bin[2] to 1: 100 -> 101
  • Use rule 1 to change bin[1] to 1: 101 -> 111
  • Use rule 2 to change bin[2] to 0: 111 -> 110
  • Use rule 1 to change bin[0] to 0: 110 -> 010
  • Use rule 2 to change bin[2] to 1: 010 -> 011
  • Use rule 1 to change bin[1] to 0: 011 -> 001
  • Use rule 2 to change bin[2] to 0: 001 -> 000

For this number, 7 operations are required to convert it to 0.

Note: In the binary representation of a number, the binary digit's positions are numbered from 0 to (x - 1) from left to right, where (x) is the number of digits in the binary representation of the number.

Input Format

The first line contains a long integer, (n).

Output Format

  • int: the minimum number of operations required to convert (n) to 0.

Constraints:

  • 1 <= n <= 10^15

Example


Input 

13

Output:

9

Explanation:

The binary representation of 13 is 1101. This is the sequence of the 9 operations that change 13 to 0 according to the constraints:

1101 -> 1100 -> 0100 -> 0101 -> 0111 -> 0110 -> 0010 -> 0011 -> 0001 -> 0000