Powerful Integer

JavaView on GFG

Time: O(log(bound)^2)

Space: O(log(bound)^2)

Intuition

Find all unique powerful integers: x^i + y^j <= bound for i,j >= 0.

Algorithm

1Iterate i starting from 0 while x^i <= bound. Iterate j while x^i+y^j <= bound. Collect unique values.

Common Pitfalls

•Same as LC 970. Handle x=1 or y=1 specially (loop at most once). Use set for uniqueness.

Powerful Integer.java

Java

// Approach: Brute force: for all x^i*y^j <= bound, add to set. Return set size.
// Time: O(log(bound)^2) Space: O(log(bound)^2)
class Solution {
    public int powerfulInteger(int[][] interval, int k) {
        int max = 0;
        for (int i = 0; i < interval.length; i++) {
            if (interval[i][1] > max)
                max = interval[i][1];
        }

        int[] arr = new int[max + 2];
        for (int i = 0; i < interval.length; i++) {
            arr[interval[i][0]] += 1;
            arr[interval[i][1] + 1] -= 1;
        }

        for (int i = 1; i < max + 2; i++)
            arr[i] = arr[i - 1] + arr[i];

        for (int i = max + 1; i >= 0; i--) {
            if (arr[i] >= k)
                return i;
        }

        return -1;
    }
}

Was this solution helpful?