Блог пользователя kstheking

JP Morgan Interview Question — Help Needed
Автор kstheking, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Now that I think about it, I should have just used bfs, typing code while someone is looking at you can cause brain to stop working :(

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can connect edges between two numbers satisfying either the operation 1 or operation 2.(Since there can be atmost two edges from a point)
And do this for all i <=1e5 then simply apply bfs from n.

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Like you said, in an interview it makes sense to just do BFS and solve the problem that way. Interviews are not going to ask you about complicated algorithms.

But, since this is Codeforces... This question is asking you to convert a number from Gray code to binary, so something like this function should work (read the link for full explanation):

int GrayToBinary32(int num)
{
    num ^= num >> 16;
    num ^= num >>  8;
    num ^= num >>  4;
    num ^= num >>  2;
    num ^= num >>  1;
    return num;
}
→ Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится -15 Проголосовать: не нравится

There's a neat observation here that you missed.

Observation

So, in general, it takes you pow(2, K) operations to take you from pow(2, K) to pow(2, K-1).

And any number is nothing but the summation of powers of 2.

So, for 13 which is 1101 it'll take you Ans(1) + Ans(4) + Ans(8) operations to reach 0 :)

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I thought of something like this, but apparently simply adding the steps for all powers won't give the answer as there were input whose value was greater than 8 but their minimum steps less than 15

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you provide a sample input like that? I am unable to find any

      Edit: I found one I think for 12 we will get less number of steps that 8

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Isn't that the binary reflected gray of 8 . The problem is confusing but when I read it from 0000 to 1000 , the first four conversions made it clear .

I think I have this in my second year course this year , but it's not a coding subject though...

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

We can use dp. Let dp[k] = cost of erasing bit k if all other bits are 0. dp[k] = 2*dp[k-1]+1 (base: dp[0]=1). I will explain why.

If there is only one bit: Add a bit to its right, erase the left bit with operation 2 then erase the bit you added. This is equal to dp[k].

If there are more bits: You are trying to reach the leftmost bit by building bits(like a ladder). If there are some bits already, then it should be easier to reach the left most bit. Subtract the cost of right bits. The cost of some number N is = Cost(N) = dp[leftmost]-Cost(N-(1<<leftmost))

int dp[32];
int main() {
    int n;
    cin >> n;
    dp[0] = 1;
    for(int i = 1;i<n;i++)dp[i] = 2*dp[i-1]+1;
    int ans = 0, sign = 1;
    for(int i = 31;i > -1;i--){
        if(n & (1<<i)){
            ans += sign*dp[i];
            sign = -sign;
        }
    }
    cout << ans;
    return 0;
}
→ Ответить