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

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

Follow up