{"id":8642,"date":"2021-10-25T20:10:37","date_gmt":"2021-10-26T03:10:37","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8642"},"modified":"2021-10-25T20:11:41","modified_gmt":"2021-10-26T03:11:41","slug":"leetcode-2048-next-greater-numerically-balanced-number","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2048-next-greater-numerically-balanced-number\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2048. Next Greater Numerically Balanced Number"},"content":{"rendered":"\n

An integer x<\/code> is numerically balanced<\/strong> if for every digit d<\/code> in the number x<\/code>, there are exactly<\/strong> d<\/code> occurrences of that digit in x<\/code>.<\/p>\n\n\n\n

Given an integer n<\/code>, return the smallest numerically balanced<\/strong> number strictly greater<\/strong> than <\/em>n<\/code>.<\/em><\/p>\n\n\n\n

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

Input:<\/strong> n = 1\nOutput:<\/strong> 22\nExplanation:<\/strong> \n22 is numerically balanced since:\n- The digit 2 occurs 2 times. \nIt is also the smallest numerically balanced number strictly greater than 1.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 1000\nOutput:<\/strong> 1333\nExplanation:<\/strong> \n1333 is numerically balanced since:\n- The digit 1 occurs 1 time.\n- The digit 3 occurs 3 times. \nIt is also the smallest numerically balanced number strictly greater than 1000.\nNote that 1022 cannot be the answer because 0 appeared more than 0 times.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> n = 3000\nOutput:<\/strong> 3133\nExplanation:<\/strong> \n3133 is numerically balanced since:\n- The digit 1 occurs 1 time.\n- The digit 3 occurs 3 times.\nIt is also the smallest numerically balanced number strictly greater than 3000.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 0 <= n <= 106<\/sup><\/code><\/li><\/ul>\n\n\n\n
    Solution: Permutation<\/strong><\/h2>\n\n\n\n
    Time complexity: O(log(n)!)
    Space complexity: O(log(n)) ?<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int nextBeautifulNumber(int n) {\n    const string t = to_string(n);\n    vector nums{1,\n                     22,\n                     122, 333,\n                     1333, 4444,\n                     14444, 22333, 55555,\n                     122333, 155555, 224444, 666666};\n    int ans = 1224444;\n    for (int num : nums) {\n      string s = to_string(num);\n      if (s.size() < t.size()) continue;\n      else if (s.size() > t.size()) {\n        ans = min(ans, num);\n      } else { \/\/ same length \n        do {\n          if (s > t) ans = min(ans, stoi(s));\n        } while (next_permutation(begin(s), end(s)));\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x. Given an integer n, return the smallest numerically balanced number strictly greater than n. Example 1: Input: n…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[177,121,42],"class_list":["post-8642","post","type-post","status-publish","format-standard","hentry","category-searching","tag-medium","tag-permutation","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8642","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=8642"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8642\/revisions"}],"predecessor-version":[{"id":8644,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8642\/revisions\/8644"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8642"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8642"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8642"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}