{"id":4607,"date":"2019-01-05T20:37:25","date_gmt":"2019-01-06T04:37:25","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4607"},"modified":"2019-01-05T20:40:14","modified_gmt":"2019-01-06T04:40:14","slug":"leetcode-970-powerful-integers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-970-powerful-integers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 970. Powerful Integers"},"content":{"rendered":"\n

Given two non-negative integers x<\/code> and y<\/code>, an integer is powerful<\/em> if it is equal to x^i + y^j<\/code> for some integers i >= 0<\/code> and j >= 0<\/code>.<\/p>\n\n\n\n

Return a list of all powerful<\/em> integers that have value less than or equal to bound<\/code>.<\/p>\n\n\n\n

You may return the answer in any order.  In your answer, each value should occur at most once.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>x = 2, y = 3, bound = 10\nOutput: <\/strong>[2,3,4,5,7,9,10]\nExplanation: <\/strong>\n2 = 2^0 + 3^0\n3 = 2^1 + 3^0\n4 = 2^0 + 3^1\n5 = 2^1 + 3^1\n7 = 2^2 + 3^1\n9 = 2^3 + 3^0\n10 = 2^0 + 3^2\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>x = 3, y = 5, bound = 15\nOutput: <\/strong>[2,4,6,8,10,14]\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  • 1 <= x <= 100<\/code><\/li>
  • 1 <= y <= 100<\/code><\/li>
  • 0 <= bound <= 10^6<\/code><\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Time complexity: O(log(bound) \/ log(x) * log(bound) \/ log(y))
    Space complexity: O(log(bound) \/ log(x) * log(bound) \/ log(y))<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 4 ms\nclass Solution {\npublic:\n  vector powerfulIntegers(int x, int y, int bound) {        \n    unordered_set ans;\n    for (int a = 1; a < bound; a *= x) {\n      for (int b = 1; a + b <= bound; b *= y) {\n        ans.insert(a + b);\n        if (y == 1) break;\n      }\n      if (x == 1) break;\n    }\n    return {begin(ans), end(ans)};\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[222,82,31],"class_list":["post-4607","post","type-post","status-publish","format-standard","hentry","category-math","tag-easy","tag-hashtable","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4607","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4607"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4607\/revisions"}],"predecessor-version":[{"id":4610,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4607\/revisions\/4610"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}