Ninja’s Base

Easy
0/40
Average time to solve is 10m
profile
Contributed by
1 upvote
Asked in companies
AdobeExotel Techcom Private Limited

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
7
21
Sample Output 1 :
2
4
Explanation For Sample Input 1 :
Test Case 1 :

For the first test case, the given number is ‘7’ so we return ‘2’ as we can write ‘7’ = 2 ^ 2 + 2 ^ 1 + 2 ^ 0’. Thus, ‘7’ base ‘2’ is ‘1 1 1’ and 2 is the smallest such number.

Test Case 2 :

For the first test case, the given number is ‘21’ so we return ‘4’ as we can write ‘21 = 4 ^ 2 + 4 ^ 1 + 4 ^ 0’. Thus, ‘21’ base ‘4’ is ‘1 1 1’ and 4 is the smallest such number.
Sample Input 2 :
2
6
15
Sample Output 1 :
5
2
Hint

Can you think of starting from the smallest number(2) and traverse upto the number looking for a ‘NINJA BASE’?

Approaches (2)
Brute 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.
Time Complexity

O(N * log(N)), where ‘N’ is the given number.

 

As we are iterating the number starting from in worst-case time complexity can be O(N) and while loop complexity is O(log(N) ) as we are dividing the number by ‘I’ in every iteration.

Space Complexity

O(1)

 

Since we are using constant space.

Code Solution
(100% EXP penalty)
Ninja’s Base
Full screen
Console