Base Conversion

Easy
0/40
Average time to solve is 15m
profile
Contributed by
10 upvotes
Asked in companies
PayPalUberAdobe

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
10 2
20 2
Sample Output 1:
2
-1
Explanation of Sample Input 1:
Test Case 1 :  
Given N = 10 and Base = 2. 
Decimal equivalent of 10 from base 2 = 2. 

Test Case 2 : 
Given N = 20 and Base = 2. 
We cannot have digit ‘2’ in a number of base 2. So, a decimal equivalent of this number is not possible. Hence, we need to print -1.
Sample Input 2:
2
B 16 
A 11
Sample Output 2:
11
10
Explanation of Sample Input 2:
Test Case 1 :  
Given N = B and Base = 16. 
Decimal equivalent of B from base 16 = 11. 

Test Case 2 : 
Given N = A and Base = 16.  
Decimal equivalent of A from base 11 = 10
Hint

Think of a solution similar to binary to decimal conversion.

Approaches (1)
Base Conversion


 

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’.
Time Complexity

O(N), where N is the total number of digits in the given number.

 

Here, we are running a single loop to calculate the decimal equivalent of a number that takes O(N) time.

Space Complexity

O(1).

 

No extra space is being used.

Code Solution
(100% EXP penalty)
Base Conversion
Full screen
Console