Last Updated: 11 Dec, 2020
Free from cubes
Moderate
The ultimate ninja Ankush was bored so his friend ninja Nikhil gave him a number and asked the ultimate ninja to tell if the number is a “CUBE FREE NUMBER” or not? And if it is then tell its position.
A cube-free number is a number whose none of the divisors is a cube number (A cube number is a cube of an integer like 8 (2 * 2 * 2) , 27 (3 * 3 * 3) ). So cube free numbers are 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18 etc (we will consider 1 as cube free). 8, 16, 24, 27, 32, etc are not cube-free numbers. So the position of 1 among the cube-free numbers is 1, the position of 2 is 2, 3 is 3, and the position of 10 is 9.
More formally, given a positive number you have to say if it's a cube-free number and if yes then tell its position among cube-free numbers, else return -1.
For example
Given:
‘N’ = 4, Yes 4 is a cube-free number since it's only divisor 2 is not a cube of any number and the position of 4 is 4 itself as a cube free number.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The following ‘T’ lines contain a single integer ‘N’, denoting the number given to us.
Output Format :
For each test case, You are supposed to return an integer that denotes the minimum steps it takes to reduce the number to 1.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10 ^ 5
Time Limit: 1sec.
Approaches
The idea is to maintain a sieve of size ‘N’ which stores -1 if the number is not a cube free number else stores the position of the number in the cube free sequence.
The steps are as follows:
- We will maintain an array of size ‘N + 1’ ‘sieve’ which stores the information w.r.t. to if it is cube free or not.
- We will process the ‘sieve’ using a helper function ‘preProcess’, which takes ‘sieve’ as its only input parameter, and process the sieve but the return type is void.
- We will traverse from 1 to 100 using ‘i’,since ‘N’ can be at max 10 ^ 5, (10 ^ 2) ^ 3 > 10 ^ 5:
- Maintain a variable ‘k’ which represents the cube of ‘i’.
- Loop from ‘k’ to ‘N’ and at each iteration take a jump of length ‘k’.
- Mark ‘sieve[k]’ as -1.
- We will traverse from 1 to ‘N’ and maintain a position variable ‘pos’ = 1.
- If ‘sieve[i]’ is not equal to -1, assign ‘sieve[i]’ as ‘pos’.
- Increment ‘pos’ by 1.
- Return ‘sieve[N]’ as the final result.