Base 58

Easy
0/40
Average time to solve is 15m
55 upvotes
Asked in companies
FacebookUber

Problem statement

You are given a number N. Your goal is to convert the number into base 58.

The Base58 alphabet consists of the following characters: “123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz”

Each byte value from 0 to 57 maps to the alphabet above.

Conversion Eg: ( according to above mapping).

Base 10 | Base 58
0       |     1  
1       |     2  
10      |     A  
20      |     L
30      |     W 
53      |     u
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains ‘T’ denoting the number of test cases.

The first and the only line of each test case contains an integer N.
Output Format: 
For each test case, print a single line containing a single integer denoting the number in the base 58.

The output of each test case will be printed in a separate line.

Note:

You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 50
0 <= N <= 10 ^ 4

Time limit: 1 sec.
Sample Input 1:
2
10
67
Sample Output 1:
B
2A
Explanation for Sample Input 1:
In test case 1:

If we represent 10 in powers of 58, it will be, 10 = 10*(58^0)
10 in base 10 corresponds to B in base 58 ( according to the above mapping).
Thus our answer is: B

In test case 2:

If we represent 66 in powers of 58, it will be, 67 = 1*(58^1) + 9*(58^0)
1 in base 10 corresponds to 2 in base 58, 9 in base 10 corresponds to A in base 58.
Thus our answer is: 2A
Sample Input 2:
3
4364
1786
6978
Sample Output 2:
2JF
Xo
35K
Hint

Convert N into powers of 58.

Approaches (1)
base 58

You can represent the integers as powers of 58 and then convert them using the above mapping.

 

Eg: 4364 =  1 * (58 ^ 2)+ 17 * (58 ^ 1) + 14 * (58 ^ 0)

1 in base 10 = 2 in base 58, 17 in base 10 = 2 in base J, 14 in base 10 = 2 in base F

Therefore the answer will be: 2JF

 

Algorithm:

  • If the number itself is 0, the answer is 1, else we do the following until the number reaches 0.
    • First, we Initiate an empty string res = ““:
    • We take the remainder of N from 58, and convert it according to the encoding in base 58 and prepend it into res.
      • res= x  + res  , x is the converted character.
    • We divide the number N by 58 and repeat the above step until N reaches 0.
Time Complexity

O(log58(N)), where ‘N’ is the given integer.

 

As we are repeatedly dividing the integer by 58, we will only have O( log58(N)) steps before the number reaches zero.

Space Complexity

O(log58(N)), where ‘N’ is the given integer.

 

We create a new string whose length will be O(log58(N)).

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