# URL Shortener

Posted: 8 Jan, 2021

Difficulty: Easy

#### 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).

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:
- Add ‘CODE[N%62]’ to ‘ANSWER’.
- Divide ‘N’ by 62.

- After the loop, breaks add ‘CODE[N]’ to ‘ANSWER’.
- Reverse our ‘ANSWER’.
- Finally, return the ‘ANSWER’.

SIMILAR PROBLEMS

# Shortest Common Supersequence

Posted: 4 Mar, 2022

Difficulty: Hard

# Mining Diamonds

Posted: 4 Mar, 2022

Difficulty: Hard

# Minimum Number of Deletions and Insertions

Posted: 4 Mar, 2022

Difficulty: Moderate

# Can You Print

Posted: 14 Apr, 2022

Difficulty: Easy

# Prime Digit Sum

Posted: 17 Apr, 2022

Difficulty: Hard