|
6 | 6 | importjava.util.List; |
7 | 7 | importjava.util.Set; |
8 | 8 |
|
9 | | -/** |
10 | | - * 970. Powerful Integers |
11 | | - * |
12 | | - * 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. |
13 | | - * |
14 | | - * Return a list of all powerful integers that have value less than or equal to bound. |
15 | | - * |
16 | | - * You may return the answer in any order. In your answer, each value should occur at most once. |
17 | | - * |
18 | | - * Example 1: |
19 | | - * |
20 | | - * Input: x = 2, y = 3, bound = 10 |
21 | | - * Output: [2,3,4,5,7,9,10] |
22 | | - * Explanation: |
23 | | - * 2 = 2^0 + 3^0 |
24 | | - * 3 = 2^1 + 3^0 |
25 | | - * 4 = 2^0 + 3^1 |
26 | | - * 5 = 2^1 + 3^1 |
27 | | - * 7 = 2^2 + 3^1 |
28 | | - * 9 = 2^3 + 3^0 |
29 | | - * 10 = 2^0 + 3^2 |
30 | | - * |
31 | | - * Example 2: |
32 | | - * |
33 | | - * Input: x = 3, y = 5, bound = 15 |
34 | | - * Output: [2,4,6,8,10,14] |
35 | | - * |
36 | | - * |
37 | | - * Note: |
38 | | - * 1 <= x <= 100 |
39 | | - * 1 <= y <= 100 |
40 | | - * 0 <= bound <= 10^6 |
41 | | - */ |
42 | 9 | publicclass_970 { |
43 | | -publicstaticclassSolution1 { |
44 | | -/**This approach results in Time Limit Exceeded since it's apparently doing |
45 | | - * redundant checks.*/ |
46 | | -publicList<Integer>powerfulIntegers(intx,inty,intbound) { |
47 | | -Set<Integer>result =newHashSet<>(); |
48 | | -intsmall =x; |
49 | | -intbig =y; |
50 | | -if (x >y) { |
51 | | -small =y; |
52 | | -big =x; |
53 | | - } |
54 | | -intmaxPower =bound /small; |
55 | | -for (inti =0;i <=maxPower +1;i++) { |
56 | | -for (intj =0;j <=maxPower +1;j++) { |
57 | | -intsum = (int) (Math.pow(small,i) +Math.pow(big,j)); |
58 | | -if (sum <=bound) { |
59 | | -result.add(sum); |
60 | | - } |
| 10 | +publicstaticclassSolution1 { |
| 11 | +/** |
| 12 | + * This approach results in Time Limit Exceeded since it's apparently doing |
| 13 | + * redundant checks. |
| 14 | + */ |
| 15 | +publicList<Integer>powerfulIntegers(intx,inty,intbound) { |
| 16 | +Set<Integer>result =newHashSet<>(); |
| 17 | +intsmall =x; |
| 18 | +intbig =y; |
| 19 | +if (x >y) { |
| 20 | +small =y; |
| 21 | +big =x; |
| 22 | + } |
| 23 | +intmaxPower =bound /small; |
| 24 | +for (inti =0;i <=maxPower +1;i++) { |
| 25 | +for (intj =0;j <=maxPower +1;j++) { |
| 26 | +intsum = (int) (Math.pow(small,i) +Math.pow(big,j)); |
| 27 | +if (sum <=bound) { |
| 28 | +result.add(sum); |
| 29 | + } |
| 30 | + } |
| 31 | + } |
| 32 | +List<Integer>list =newArrayList<>(result); |
| 33 | +Collections.sort(list); |
| 34 | +returnlist; |
61 | 35 | } |
62 | | - } |
63 | | -List<Integer>list =newArrayList<>(result); |
64 | | -Collections.sort(list); |
65 | | -returnlist; |
66 | 36 | } |
67 | | - } |
68 | 37 |
|
69 | | -publicstaticclassSolution2 { |
70 | | -/** credit: https://leetcode.com/problems/powerful-integers/discuss/214212/JavaC%2B%2BPython-Brute-Force */ |
71 | | -publicList<Integer>powerfulIntegers(intx,inty,intbound) { |
72 | | -Set<Integer>result =newHashSet<>(); |
73 | | -for (inti =1;i <bound;i *=x >1 ?x :bound +1) { |
74 | | -for (intj =1;i +j <=bound;j *=y >1 ?y :bound +1) { |
75 | | -result.add(i +j); |
| 38 | +publicstaticclassSolution2 { |
| 39 | +/** |
| 40 | + * credit: https://leetcode.com/problems/powerful-integers/discuss/214212/JavaC%2B%2BPython-Brute-Force |
| 41 | + */ |
| 42 | +publicList<Integer>powerfulIntegers(intx,inty,intbound) { |
| 43 | +Set<Integer>result =newHashSet<>(); |
| 44 | +for (inti =1;i <bound;i *=x >1 ?x :bound +1) { |
| 45 | +for (intj =1;i +j <=bound;j *=y >1 ?y :bound +1) { |
| 46 | +result.add(i +j); |
| 47 | + } |
| 48 | + } |
| 49 | +returnnewArrayList<>(result); |
76 | 50 | } |
77 | | - } |
78 | | -returnnewArrayList<>(result); |
79 | 51 | } |
80 | | - } |
81 | 52 | } |