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

Need a help for a question
Автор failure_forever, история, 20 месяцев назад, По-английски

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

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

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

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

→ Ответить
»
20 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится 
/*
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)

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

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

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

      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.)

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

    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)
*/
    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      can you please provide me a pseudo code your approach

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

        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)
        → Ответить
        • »
          »
          »
          »
          »
          20 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

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

            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.

            → Ответить