### harshit2001411's blog

By harshit2001411, history, 2 months ago,

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

 » 2 months ago, # |   0 I also got the same question. But it wasn't canceled in our case. Which day did you attempted the test?
•  » » 2 months ago, # ^ |   0 On 29th July, First shift
 » 2 months ago, # | ← 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 :(
•  » » 2 months ago, # ^ |   +3 Yes that was what i do not wanted to do, write those functions.
 » 2 months ago, # |   0 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 →   +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++ solutionIdeone.com
•  » » 2 months ago, # ^ |   0 Thank you for the explanation. I didn't knew about __int128 till this question.
•  » » 7 weeks ago, # ^ |   0 In some compilers this __int128 is not working :(
 » 2 months ago, # |   0 See this : https://www.hackerrank.com/contests/goc-cdc-series-10/challenges/itsybitsy/problem If it is not accessible then tell me.
•  » » 2 months ago, # ^ |   0 It is accessible, thank you. It's literally the same question!
 » 2 months ago, # |   0 I have attempted the problem in python