URL Shortener

PROBLEM STATEMENT

You have given a URL id – 'N' consisting of only digits. Your task is to generate a short URL for the given URL id.

To generate a short URL, you need to convert the given URL id to 62 base number where digits of the number are:[“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”] i.e “0” corresponds to 0, “a” corresponds to 10, “Z” corresponds to 61, and “10” corresponds to 62, “11” corresponds to 63, and so on….

Follow Up:

Can you solve this in logarithmic time and space complexity?

Input format :

The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test contains a single integer 'N', denoting the URL id.

Output format :

For each test case, return a short URL for the URL id.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 1000  
0 <= N <= 10^18 

Time limit: 1sec

Approach 1

The idea here is to use recursion and generate a short URL. We will start from the last digit of ‘N’ and add its corresponding modulo 62 code to answer the string and then divide ‘N’ by 62. Finally, we reverse the answer string to get a short URL.

The Steps are as follows:

Declare a string of 62 characters where each index corresponds to a particular code of shortened URL, say ‘CODE’.
Then, declare an empty string to store our shortened URL, say ‘ANSWER’.
Call the shortUrlRecursion function.
Reverse the ‘ANSWER’.
Finally, return the ‘ANSWER’.

void shortUrlRecursion(‘ANSWER’, ‘N’):

Define base case if ‘N’ < 62 then add ‘CODE[N]' to ‘ANSWER’ and return.
Add ‘CODE[N%62]' to ‘ANSWER’
Recur for shortUrlRecursion(‘ANSWER’, ‘N’ / 62).

Try Problem

Approach 2

The idea here is similar to finding a binary representation of a number. We keep dividing ‘N’ with 62 and its corresponding code to answer until it becomes < 62. Then finally add ‘CODE[N]’ to answer and reverse our answer.

The Steps are as follows:

Declare a string of 62 characters where each index corresponds to a particular code of shorten URL, say ‘CODE’.
Let’s declare an empty string to store our shorten URL, say ‘ANSWER’.
Run a loop until ‘N’ greater than 61, and do:
1. Add ‘CODE[N%62]’ to ‘ANSWER’.
2. Divide ‘N’ by 62.
After the loop, breaks add ‘CODE[N]’ to ‘ANSWER’.
Reverse our ‘ANSWER’.
Finally, return the ‘ANSWER’.

Try Problem