970. Powerful Integers #

Problem #

Given two positive integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

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

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]

Note:

• 1 <= x <= 100
• 1 <= y <= 100
• 0 <= bound <= 10^6

Problem Summary #

Given two positive integers x and y, if an integer is equal to x^i + y^j, where integers i >= 0 and j >= 0, then we consider this integer to be a powerful integer. Return a list of all powerful integers whose values are less than or equal to bound. You may return the answer in any order. In your answer, each value should occur at most once.

Solution Approach #

• A simple problem. The task requires finding all solutions that satisfy x^i + y^j ≤ bound. Since the output must not contain duplicates, use a map for deduplication. The rest is to brute-force enumerate all solutions with an n^2 nested loop.

Code #

package leetcode

import "math"

func powerfulIntegers(x int, y int, bound int) []int {
	if x == 1 && y == 1 {
		if bound < 2 {
			return []int{}
		}
		return []int{2}
	}
	if x > y {
		x, y = y, x
	}
	visit, result := make(map[int]bool), make([]int, 0)
	for i := 0; ; i++ {
		found := false
		for j := 0; pow(x, i)+pow(y, j) <= bound; j++ {
			v := pow(x, i) + pow(y, j)
			if !visit[v] {
				found = true
				visit[v] = true
				result = append(result, v)
			}
		}
		if !found {
			break
		}
	}
	return result
}

func pow(x, i int) int {
	return int(math.Pow(float64(x), float64(i)))
}