JP Morgan Interview Question — Help Needed

Revision en2, by kstheking, 2020-09-02 09:31:26

Hello, this is a question asked to me in the JP Morgan Interview and I had no idea how to solve it, please tell me how you would have approached this problem or how would you go about solving it, because I couldn't find any pattern or how do I implement it

Question: Given a number, find the minimum number of steps you need to convert it to 0, you are allowed the following two operations

Operation 1: Change the last binary digit of the number
Example: 8 which in binary is (1000) you can convert the last 0 to 1 or vice versa so 1000 -> 1001

Operation 2: If at a position the binary digit is 1, and all binary digits to its right are 0 then you can change the binary digit to the left of that position
Example: in 1001 for the last binary digit it is 1, and there are no 1s to its right therefore we can change the binary digit to its left, as 1001 -> 1011

Constraints: 1 <= n <= 1e5

Example: for input 8 it will take 15 steps
1000 -> 1001 -> 1011 -> 1010 -> 1110 -> 1111 -> 1101 -> 1100 -> 0100 -> 0101 -> 0111 -> 0110 -> 0010 -> 0011 -> 0001 -> 0000

Tags binary, #interview

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kstheking 2020-09-02 09:31:26 3 Tiny change: 'ration 2:_If at a po' -> 'ration 2:_ If at a po'
en1 English kstheking 2020-09-02 08:18:27 1152 Initial revision (published)