Last Updated: 21 Apr, 2021

Ninja’s Base

Easy

Asked in companies

Solve now

Problem statement

One day Ninja asks for one day's leave from his trainer. His trainer agrees with him only if he would complete a task. The task is that Ninja has to find the smallest 'NINJA BASE' of a number ‘N’. We call ‘B >= 2’ a ‘NINJA BASE’, if all digits of ‘N’ base ‘B’ can be written as ‘1s’.

Example :

Suppose given number is ‘13’ so we return ‘3’ as the answer as we can write 13 = 3 ^ 2 + 3 ^ 1 + 3 ^ 0. '3' is the smallest number 'B for which 13 base 'B' is ‘1 1 1’. So, the 'NINJA BASE' of 'N' = 13 is 3.

Given number 'N', your task is to help Ninja find its ‘NINJA BASE’.

Note :

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Input Format :

The first line of input contains a ‘T’ number of test cases.
The first line of each test case contains an integer ‘N’ denoting the given number.

Output Format :

For each test case, return the smallest ‘NINJA BASE’.

Constraints :

1 <= T <= 10 ^ 4
3 <= N <= 10 ^ 6

Time Limit: 1 second

Follow Up:

Can you do this in O(logN) time and constant space?

Solve now

Approaches

01 Approach

The idea here is starting from the smallest number i.e. ‘2’, we traverse up to the given number. Starting from ‘2’, we check if we can write the number ‘N’ in form of base ‘i’. If so, we say that the number ‘i’ is ‘NINJA BASE’ else we increase its value.

Run a loop starting from ‘i’ = ‘2’ and up to the given number ‘N’.
- Store the number in variable ‘TEMP’ and declare a bool variable ‘FLAG’ and initialize it with ‘TRUE’.
  - Run another while loop until ‘TEMP > 0’
    - In every iteration we check
      - If ‘TEMP % i == 1’ we divide the ‘TEMP = TEMP / i’ and continue the loop as there is the chance that we can write it in the base form.
      - Else we make the ‘FLAG’ as ‘FALSE’ and break from the loop.
- If ‘FLAG == TRUE’ return ‘i’ as it is the smallest required base.
Else continue the loop.

Solve now

02 Approach

The idea here is to use binary search as according to our constraints number can be up to 10 ^ 6 so the maximum length of the representation possible is up to ‘17’. So in every step of binary search, we can say if the power of mid raised to the max is smaller than the number, we have to increase our start else we can decrease our end where start represents ‘2’ as the smallest base possible is ‘2’. We say ‘N - 1’ is our end as the largest base possible is ‘N - 1’.

Run a loop starting from ‘i’ = ‘17’ up to the ‘i > 2’.
- Initialize ‘START’ and ‘END’ with ‘2’ and ‘N - 1’ respectively.
- Run another loop until ‘START’ <= ‘END’.
- Declare ‘MID’ where MID = (START + END) / 2;
- Now check the power of MID raise to ‘i’ :
  - If greater than ‘N’, ‘END = MID - 1’. We say our possible base must be less than ‘MID’.
  - If less than ‘N’, ‘START = MID + 1’. We can say our possible base must be greater than ‘MID’.
  - Else return ‘MID’ as we found the required base.
If we reach the end of the loop, no number is found, so we return the biggest possible i.e. ‘N -1’.

Solve now