Free from cubes

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.

Sample Input 1 :

2
4
8

Sample Output 1 :

4
-1

Explanation of the Sample Input 1:

In the first test case, Yes 4 is a cube-free number since its only divisor 2 is not a cube of any number and the position of 4 is 4 itself as a cube-free number.

In the second test case, Since one of the divisors of 8 is 8 itself which is 2 * 2 * 2, i.e., a cube of 2 hence 8 is not a cube-free number.

Sample Input 2 :

2
9
10

Sample Output 2 :

8
9
Hint

Can we use the algorithm Sieve of Eratosthenes. which stores the position of each number from 1 to ‘N’?

Approaches (1)
Sieve of Eratosthenes

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.
Time Complexity

O(N), Where ‘N’ is the number given to us.

 

Since we are traversing from 1 to N, therefore the overall time complexity will be O(N). 

Space Complexity

O(N), Where ‘N’ is the number given to us.


Since we are using an array of size ‘N’. Hence the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Free from cubes
Full screen
Console