harshit2001411's blog

Uber Coding Round Problem
By harshit2001411, history, 3 years 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

Comments Comments (9)
| Write comment?
»
3 years 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?

→ Reply
»
3 years 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 :(

→ Reply
»
3 years 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
→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

See this : https://www.hackerrank.com/contests/goc-cdc-series-10/challenges/itsybitsy/problem
If it is not accessible then tell me.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have attempted the problem in python

→ Reply