Powerful Divisors

Asked in:
lenskart

Problem Description

You are given an integer array A of length N.
For every integer X in the array, you have to find out the number of integers Y, such that 1 <= Y <= X, and the number of divisors of Y is a power of 2.

For example, 6 has the following divisors - [1, 2, 3, 6]. This is equal to 4, which is a power of 2.
On the other hand, 9 has the following divisors [1, 3, 9] which is 3, which is not a power of 2.

Return an array containing the answer for every X in the given array.

Problem Constraints

1 <= N <= 10⁵
1 <= A_max <= 10⁶
Sum of A_max over all test cases will not exceed 5 * 10⁶

Input Format

The first argument is the integer array A.

Output Format

Return an array containing the answer for every X in the given array.

Example Input

Input 1:

A = [1, 4]

Input 2:

A = [5, 10]

Example Output

Output 1:

[1, 3]

Output 2:

[4, 8]

Example Explanation

Explanation 1:

The numbers 1, 2, 3 have the required number of divisors.

Explanation 2:

Only 4 and 9 are the numbers less than or equal to 10 which do not have the required number of divisors.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving Powerful Divisors on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

Asked In:

lenskart

Powerful Divisors

Discussion