Question

NVIDIA | OA | SDE | Set - 1 |

Answer 1

 

int minStep(long n) {
    int one = __builtin_popcountl(n);
    if (one <= 1) return one;
    return 1 + min(minStep(n+(n&(-n))), minStep(n-(n&(-n))));
}

Answer 2

Description
Given a positive integer n, return the minimum number of step to reduce n to 0.
In one step, you can add or subtract a power of two (2^i, i >= 0).

 

Example 1

 

Input: 14
Output: 2
Explanation: 14(01110) -> 16(10000) -> 0

 

Example 2

 

Input: 27
Output: 3
Explanation: 27(011011) -> 31(011111) -> 32(100000) -> 0

 

Example 3

 

Input: 1
Output: 1