harshit2001411's blog

By harshit2001411, history, 2 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

essentially divide by the bin string 110 (aka 6), where the remainder (when put into base 6 ) is the digit of the ith column. then apply this process again to the number until you are left with nothing.

division in base 2 is a similar process to how humans do base 10 division on paper.

»
2 months ago, # |
Rev. 24   Vote: I like it +10 Vote: I do not like it

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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the explanation. I didn't knew about __int128 till this question.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In some compilers this __int128 is not working :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have attempted the problem in python