New update is available. Click here to update.

Base Conversion

PROBLEM STATEMENT

You are given a number ‘N’ as a string in base ‘B’. Your task is to convert ‘N’ in base 10. If it’s impossible to convert ‘N’ into base 10, then you need to print -1.

Note :

1. ‘N’ contains only digits ‘0’ to ‘9’ and English letters ‘A’ to ‘F’.
2. Decimal equivalent of 0 is 0, 1 is 1, . . .9 is 9, A is 10, B is 11, . . . F is 15.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a string ‘N’ and an integer ‘Base’ separated by a single space.

Output Format:

For each test case, print the ‘N’ in base 10. If it’s impossible to convert ‘N’ to base 10 then print -1.
The output of each test case will be printed in a separate line.

Constraints:

1 <= T <= 5
1 <= decimal( N ) <= 10 ^ 9
1 <= B  <= 16

Where ‘T’ is the number of test cases, decimal(N) is the decimal equivalent of ‘N’ and ‘B’ is the base of number ‘N’.

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Approach 1

The idea here is to use base conversion. We will simply divide the string into digits and then calculate the answer using the below formula.

num[ N – 1] * 1 + num[ N – 2 ] * base + num[N – 3] * (base) ^ 2 + . . . + num[ 0 ] * ( (base) ^ (N-1) )

Algorithm:

Declare a variable to store the decimal equivalent of num, say ‘answer’, and initialize it with zero. Also, declare a variable ‘base’ to keep track of the base for current digit and initialize it with one. Here, ‘num’ is the given number.
Run a loop from index = ‘N – 1’ to ‘index’ = 0. Here ‘N’ is the length of the number ‘N’.
Convert num[ index ] to the equivalent digit in the decimal system, say ‘digit’. Example: ‘0’ becomes 0 and ‘B’ becomes 11.
If ‘digit’ >= ‘B’, then return -1 as any digit cannot be greater or equal to the base of the number. Here, ‘B’ is given the base of the number.
Add digit * base to the ‘answer’.
Multiply ‘base’ with ‘B’ for the next iteration.
Finally, return the ‘answer’.

Try Problem