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

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

Hi, There was this one tedious problem in the Uber coding round.

Q) Given a binary string S, convert it to a base 6 equivalent number string.

S.length() >= 1 && S.length() <= 100.

My question is whether there is any faster way to do such conversions instead of the old-fashioned way of converting to base 10 and then to base 6?

PS: the round got cancelled because of the server crash.

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

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

I also got the same question. But it wasn't canceled in our case. Which day did you attempted the test?

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

Unless you want to write your own division/remainder functions for two strings (which represent numbers in some non-decimal base), you are stuck with the language's division and modulo operators which work for the int datatype which is represented in base 10 unfortunately :(

»
3 года назад, # |
Rev. 24   Проголосовать: нравится +10 Проголосовать: не нравится

The following way should be faster. Start with $$$0$$$ answer. Then, for each binary digit $$$S[i]$$$ in the given binary string $$$S$$$, where $$$0 \le i < N$$$ and $$$N = S.size()$$$: if $$$S[i] = 1$$$, then add to the answer the base-$$$6$$$ representation of $$$2^{N-1-i}$$$. In GNU C++, you can use the __int128 integer data-type to generate $$$2^p$$$ when $$$0 \le p < 127$$$, and the conversion of $$$2^{p}$$$ to base-$$$6$$$ can be done in at most $$$50$$$ iterations using repeated integer and modulo division by $$$6$$$.

Alternatively, and should be even faster, you can generate an __int128 representation of $$$S$$$, as its length does not exceed $$$100$$$ bits. Then, repeated integer and modulo division by $$$6$$$ can be used to compute the base-$$$6$$$ digits directly from this representation. Note that the computer normally uses the binary numbers system to represent integers. In other words, the base-10 digits of $$$S$$$ in decimal numbers system are not usually computed during this binary to base-$$$6$$$ conversion procedure.

Check the following implementation if interested.

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

I have attempted the problem in python