failure_forever's blog

Need a help for a question
By failure_forever, history, 20 months ago, In English

Can anyone tell me how to do this question: Binary Number. What is the intuition behind?

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's brute force. Try maintaining a carry variable along the way and handle rightmost bit.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No need for that, just convert the number to an integer.

    → Reply
»
20 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
/*
Here is my approch, Let's consider the second sample 1001001  

1001001  -> action = 0 (odd, add 1)
1001010  -> action = 1 (even, right shift by 1)
100101   -> action = 2 (odd, add 1)
100110   -> action = 3 (even, right shift by 1)
10011    -> action = 4 (add)
10100    -> action = 5 (even, right shift by 1)
1010     -> action = 6 (even, right shift by 1)
101      -> action = 7 (add)
110      -> action = 8 (even, right shift by 1)
11       -> action = 9 (add)
100      -> action = 10 (even, right shift by 1)
10       -> action = 11 (even, right shift by 1)
1        -> action = 12 (result)

*/
→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell what will be the time complexity of your solution?

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Not more that O(a), where a is the answer. Answer shouldn't be more than around 2logx + 1. (I mean base 2 log or binary log, aka lg.)

      → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    UPD: Thanks for fixing your comment.

    No. The calculations (additions) are wrong. Here is the correct sequence.

    /*
1001001  -> action = 0 (odd, add 1)
1001010  -> action = 1 (even, divide by 2)
100101   -> action = 2 (odd, add 1)
100110   -> action = 3 (divide)
10011    -> action = 4 (add)
10100    -> action = 5 (divide)
1010     -> action = 6 (divide)
101      -> action = 7 (add)
110      -> action = 8 (divide)
11       -> action = 9 (add)
100      -> action = 10 (divide)
10       -> action = 11 (divide)
1        -> action = 12 (done)
*/
    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please provide me a pseudo code your approach

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Something like this.

        str
add_one (str x)
{
  carry = '1'
  i = x.size () - 1
  while (i >= 0 && carry == '1')
    {
      if (x[i] == '1')
        x[i] = '0'
      else
        x[i] = '1', carry = '0'
    }
  if (carry == '1')
    x = '1' + x
  return x
}

string = get_input ()
x = convert_to_integer (string)
i = 0
while (x != 1)
{
  if (x.last_char () == '0') x = remove_last_char (x)
  else x = add_one (x)
  ++i
}
print (i)
        → Reply
        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          this approach will give a run time error for input 1010101001001111000111110011111000010101011111101010

          I already tried this approach then Only I looked to other's solution. If you can give some other approach then much appreciated.

          → Reply
          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, I missed that, sorry. I've updated the pseudo code. But I highly recommend you to learn how binary numbers work, they'll help you in the long run.

            → Reply