Need a help for a question

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

Автор failure_forever, история, 3 года назад, По-английски

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

-5

failure_forever
3 года назад
12

Комментарии (10)

Показать архивные | Написать комментарий?

vecna

3 года назад, скрыть # |

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

→ Ответить

AkibAzmain

3 года назад, скрыть # ^ |

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

→ Ответить

tawhidmonowar

3 года назад, скрыть # |

← Rev. 2 →

/*
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)

*/

→ Ответить

failure_forever

3 года назад, скрыть # ^ |

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

→ Ответить

AkibAzmain

3 года назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить

AkibAzmain

3 года назад, скрыть # ^ |

← Rev. 2 →

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)
*/

→ Ответить

failure_forever

3 года назад, скрыть # ^ |

can you please provide me a pseudo code your approach

→ Ответить

AkibAzmain

3 года назад, скрыть # ^ |

← Rev. 2 →

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)

→ Ответить

failure_forever

3 года назад, скрыть # ^ |

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.

→ Ответить

AkibAzmain

3 года назад, скрыть # ^ |

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.

→ Ответить