0
$\begingroup$

Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or return no number exists.

Constraints given: $2\leq base \leq 36$, No. of numbers given in different representations is N $\le$ 100, Test Cases $\leq$200, time Limit 1sec

For example,

Here $T=1,N=3$,

$1001111$

$117$

$4F$

These all represent the same number, i.e $(79)_{10}$. $(1001111)_3$ = $(117)_8$=$(4F)_{16}$ Hence answer is $79$. Whereas if any of the above number is changed to any other except those (for eg. if (1001111) is changed to something else) then the answer would be "No such number exist".

Please suggest an Efficient way with a pseudo code/code.

$\endgroup$
  • $\begingroup$ Programming competitions are off-topic here. We can help you with algorithms. $\endgroup$ – Yuval Filmus Oct 7 at 18:42
  • $\begingroup$ @Yuval Filmus, But pseudo code is the part of algorithm implementation isn't it? $\endgroup$ – Akash Tadwai Oct 8 at 2:30
  • $\begingroup$ No, it’s a way of describing algorithms. $\endgroup$ – Yuval Filmus Oct 8 at 4:28
0
$\begingroup$

Let's start with a simple algorithm. Go over all possible interpretations of the first string (using all possible bases). For each such interpretation, go over the remaining string, and check whether they equal the interpretation of the first string for one of the possible bases. If there are $m$ possible bases and $n$ digits in total, then the running time is $O(m^2 n)$, ignoring the cost of arithmetic.

We can improve this as follows. Suppose for simplicity that all strings are at least two digits long (if not, we know the value of the number, and can finish in $O(nm)$ time). Compute all possible interpretations for each string, put all of these $nm$ numbers together, and sort them. Check whether the sorted list contain $n$ identical elements. This algorithm takes $O(nm \log (nm))$ time.

Another improvement, with a slightly better running time, modifies the original approach using binary search. Go over all possible interpretations of the first string. For each such interpretation, go over the remaining string, and for each one, use binary search (on the base) to find whether they equal the interpretation of the first string for one of the possible bases. This algorithm runs in $O(nm \log m)$ time.

$\endgroup$
  • $\begingroup$ But in a programming language like C++ it would be difficult to do all the operations such as multiplication,addition of two strings etc (as the max value of a number can be $\sum_{i=0}^{n} 36^i$ which cant be stored in even long long int for some big value n). $\endgroup$ – Akash Tadwai Oct 7 at 18:40
  • $\begingroup$ Use a library such as GMP. $\endgroup$ – Yuval Filmus Oct 7 at 18:41

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.