-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
970.cpp
47 lines (46 loc) · 1.43 KB
/
970.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
vector<int> res;
unordered_set<int> s;
int tx=1, ty=1, ts ;
vector<int> xs, ys;
while(1){
xs.push_back(tx);
tx*=x;
if(tx >= bound || tx==xs.back()) break;
}
while(1){
ys.push_back(ty);
ty*=y;
if(ty >= bound || ty == ys.back()) break;
}
for(int i=0; i < xs.size(); i++ ){
for(int j=0; j<ys.size(); j++){
ts = xs[i]+ys[j];
if(ts > bound) break;
s.insert(ts);
}
}
copy(begin(s), end(s), back_inserter(res));
return res;
}
};
__________________________________________________________________________________________________
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
unordered_set<int> s;
for (int i = 1; i <= bound; i *= x) {
for (int j = 1; i + j <= bound; j *= y) {
s.insert(i + j);
if (y == 1) break;
}
if (x == 1) break;
}
return vector<int>(s.begin(), s.end());
}
};
__________________________________________________________________________________________________