Powerful Integers
Simple problem: https://leetcode.com/problems/powerful-integers/description/
Code will run in up to 10^6, which is fine. Do a sieves-style, avoid Math.Pow, hash-table the solution to avoid dupes, handle cases when the input is 1 (special), other than that, two nested loops ought to do it. Thanks, ACC.
Given two non-negative 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 <= 1001 <= y <= 1000 <= bound <= 10^6
Code will run in up to 10^6, which is fine. Do a sieves-style, avoid Math.Pow, hash-table the solution to avoid dupes, handle cases when the input is 1 (special), other than that, two nested loops ought to do it. Thanks, ACC.
public class Solution
{
public IList PowerfulIntegers(int x, int y, int bound)
{
List retVal = new List();
Hashtable seen = new Hashtable();
int min = Math.Min(x, y);
int max = Math.Max(x, y);
for (int p1 = 1; p1 <= bound; p1 *= min)
{
for (int p2 = 1; p1 + p2 <= bound; p2 *= max)
{
if (!seen.ContainsKey(p1 + p2))
{
seen.Add(p1 + p2, true);
retVal.Add(p1 + p2);
}
if (max == 1) break;
}
if (min == 1) break;
}
return retVal;
}
}
Comments
That's a lot nicer than my super ugly (but crazy fast 0ms) solution in Rust :)
Reply Deleteuse std::collections::HashSet;
impl Solution {
pub fn powerful_integers(x: i32, y: i32, bound: i32) -> Vec {
let xs = if x != 1 {
let mut xs = Vec::new();
let mut v = 1;
while v <= bound {
xs.push(v);
v *= x;
}
xs
} else {
vec![1]
};
let ys = if y != 1 {
let mut ys = Vec::new();
let mut v = 1;
while v <= bound {
ys.push(v);
v *= y;
}
ys
} else {
vec![1]
};
let mut powerful: HashSet = HashSet::new();
for x in xs {
for y in &ys {
if x + y <= bound {
powerful.insert(x + y);
}
}
}
powerful.iter().map(|n| *n).collect()
}
}
https://gist.github.com/ttsugriy/a851a5e615c4aa63b5d80ca87d0e75d5
Love it! Not ugly at all, and one can’t beat 0ms, at least not in this dimension π
Reply Deleteπ€£
DeletePost a Comment
[γγ¬γΌγ ]