首页 > itarticle > powerful integers

powerful integers

admin 11月 23, 2020 0

970. Powerful Integers

描述：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.

例子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

class Solution {
      public List<Integer> powerfulIntegers(int x, int y, int bound) {
         int maxV=Math.max(x, y);
         int minV=Math.min(x, y);
         int sum;
         int sumMaxV=1;
         int sumMinV=1;
        Set<Integer> set=new HashSet<>();

        //3
         while(sumMaxV<=bound) {
             sumMinV=1;
             while(sumMinV<=(bound-sumMaxV)) {
                 sum=sumMaxV+sumMinV;
                // if(sum>bound)
                //     break;     while()条件已经判断了
                 set.add(sum);
               if(minV==1)
                     break;
                 sumMinV*=minV;
             }
             sumMaxV*=maxV;
              if(maxV==1)
                     break;
         }

         return new ArrayList<>(set);
     }
}

    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        Set<Integer> result = new HashSet<>();
        for (int a = 1; a < bound; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                result.add(a + b);
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }
        return new ArrayList<>(result);
    }
}