970. Powerful Integers
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.
Example 1:
Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 20 + 30 3 = 21 + 30 4 = 20 + 31 5 = 21 + 31 7 = 22 + 31 9 = 23 + 30 10 = 20 + 32
Example 2:
Input: x = 3, y = 5, bound = 15 Output: [2,4,6,8,10,14]
Constraints:
1 <= x, y <= 1000 <= bound <= 106
Rust Solution
struct Solution;
impl Solution {
fn powerful_integers(x: i32, y: i32, bound: i32) -> Vec<i32> {
let mut set: Vec<bool> = vec![false; bound as usize + 1];
let mut i = 0;
while x.pow(i) < bound {
let mut j = 0;
while y.pow(j) < bound {
let sum = x.pow(i) + y.pow(j);
if sum <= bound {
set[sum as usize] = true;
}
j += 1;
if y == 1 {
break;
}
}
i += 1;
if x == 1 {
break;
}
}
let mut res = vec![];
for i in 0..=bound {
if set[i as usize] {
res.push(i);
}
}
res
}
}
#[test]
fn test() {
let x = 2;
let y = 3;
let bound = 10;
let res = vec![2, 3, 4, 5, 7, 9, 10];
assert_eq!(Solution::powerful_integers(x, y, bound), res);
}
Having problems with this solution? Click here to submit an issue on github.