970. Powerful Integers

Description

Given three integers x, y, and bound, return a list of all the powerful integers that have a value less than or equal to bound.

An integer is powerful if it can be represented as xi + yj for some integers i >= 0 and j >= 0.

You may return the answer in any order. In your answer, each value should occur at most once.

Constraints

• 1 <= x, y <= 100

• 0 <= bound <= 106

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: x = 2, y = 3, bound = 10

Output: [2, 3, 4, 5, 7, 9, 10]

Explanation:

2 = 2^0 + 3^0

3 = 2^1 + 3^0

4 = 2^0 + 3^1

5 = 2^1 + 3^1

7 = 2^2 + 3^1

9 = 2^3 + 3^0

10 = 2^0 + 3^2

Example 2

Input: x = 3, y = 5, bound = 15

Output: [2, 4, 6, 8, 10, 14]

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        
        int a = x == 1 ? bound : (int) (Math.log(bound) / Math.log(x));
        int b = y == 1 ? bound : (int) (Math.log(bound) / Math.log(y));
        
        HashSet<Integer> powerfulIntegers = new HashSet<Integer>();
        
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                
                int value = (int) Math.pow(x, i) + (int) Math.pow(y, j);
                
                if (value <= bound) {
                    powerfulIntegers.add(value);
                }
                
                // No point in considering other powers of "1".
                if (y == 1) {
                    break;
                }
            }
            
            if (x == 1) {
                break;
            }
        }
        
        return new ArrayList<Integer>(powerfulIntegers);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> result = null;
        Set<Integer> powerfulInts = new HashSet();
        if(bound > 1) {
            for(int p1 = 1; p1 < bound; p1 *= x) {
                for(int p2 = 1; p1 + p2 <= bound; p2 *= y) {
                    powerfulInts.add(p1 + p2);
                    if(y == 1) {
                        break;
                    }
                }
                if(x == 1) {
                    break;
                }
            }
        }
        return new ArrayList(powerfulInts);
    }
}

Follow up