0
$\begingroup$

Given a number system with only 3 and 4. Find the nth number in the number system.

There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone please help me derive the logic for framing an algorithm for this question?

One approach that crosses my mind is, we can think of this number system as also a binary one ( in 3 and 4, instead of 1 and 0) Thus, we could possibly convert the nth number to its corresponding binary format and replace 0 with 3 and 1 with 4. One problem here though is that say the nth number is 333. This in the regular (0 and 1) binary system would be 000 = 0, which evidently is wrong since the nth number is not 0.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This seems more appropriate for Mathematics. $\endgroup$ – Yuval Filmus Mar 26 '18 at 20:59
  • $\begingroup$ The idea behind the array used is redundant, you do not need it to answer what is n-th number. Have you tried solving it another way? $\endgroup$ – Evil Mar 26 '18 at 21:04
  • $\begingroup$ If if (n == 1) return 3; else if (n == 2) return 4; else throw new ArgumentOutOfRangeException() is not the correct answer, the question needs improving. $\endgroup$ – Peter Taylor Mar 27 '18 at 7:33
  • $\begingroup$ Your idea seems good, if you take number of digits into account, 000 is 0 represented on 3 bits, conversion from binary to "34"-ary needs preserving leading zeros, to make answer "333" not "3". Besides that, you are very close to answer. $\endgroup$ – Evil Mar 27 '18 at 15:36
  • 2
    $\begingroup$ What do you mean by "a number system with only 3 and 4"? $\endgroup$ – David Richerby Mar 27 '18 at 16:49
2
$\begingroup$

You're on the right track, it is similar to binary in a way.

The first step to coming up with an efficient solution is to recognize that to convert a number from the $3,4$ system to decimal, you can treat $3$'s like a $1$ in binary, they have a value equivalent to $2^n$ where $n$ is the position of the digit, starting from the right $n$ starting at $0$. Thus $3 \equiv 1$, $33 \equiv 3$, $333\equiv 7$, etc.

A $4$ has a value equivalent to $2^{n+1}$ starting from the right $n$ starting at $0$, so $4\equiv2$, $44 \equiv 6$, etc.

Because of the similarity to binary, we can convert our input (the decimal number) to binary, and then convert that to $3,4$. To do so, we can use the following algorithm.

Given a binary number, iterate through the digits from right to left.

  1. If the digit encountered is a $1$, place a $3$ for that digit in the result.

  2. If the digit encountered is a $0$, and there are more digits following, place a $4$ for this digit in the result, and for any consecutive $0$'s, place a $3$ for those digits until a $1$ is encountered. When a $1$ is encountered following a $0$ or series of $0$'s, if there are more digits following, change this $1$ to a $0$, and repeat step $2$ as if this were the first $0$ you've encountered. When a $1$ is encountered and no more digits are following it, do nothing and return the result.

This reason this works is the following

  1. Step $1$ uses the fact that $3$ has the same value in $3,4$ as $1$ does in binary.

  2. Step $2$ is necessary because in $3,4$ there is no $0$ value for any digit. Using the fact that $2^n = 2^{n-1} \times 2 = 2^{n-1} + 2^{n-1}$ we convert a $1$ followed by $n$ $0$'s to its equivalent form in $3,4$ of $n-2$ $3$'s followed by a $4$. The first $3$ has a value of $2^{n-1}$ and the remaining $3$'s and $4$ sum up to $2^{n-1}$.

This algorithm is roughly $O(\log n)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.