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 = 1 Output: 22 Explanation: 22 is numerically balanced since: - The digit 2 occurs 2 times. It is also the smallest numerically balanced number strictly greater than 1.
Example 2:
Input: n = 1000 Output: 1333 Explanation: 1333 is numerically balanced since: - The digit 1 occurs 1 time. - The digit 3 occurs 3 times. It is also the smallest numerically balanced number strictly greater than 1000. Note that 1022 cannot be the answer because 0 appeared more than 0 times.
Example 3:
Input: n = 3000 Output: 3133 Explanation: 3133 is numerically balanced since: - The digit 1 occurs 1 time. - The digit 3 occurs 3 times. It is also the smallest numerically balanced number strictly greater than 3000.
Constraints:
0 <= n <= 106
Solution: Permutation
Time complexity: O(log(n)!)
Space complexity: O(log(n)) ?
C++
|
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 |
// Author: Huahua class Solution { public: int nextBeautifulNumber(int n) { const string t = to_string(n); vector<int> nums{1, 22, 122, 333, 1333, 4444, 14444, 22333, 55555, 122333, 155555, 224444, 666666}; int ans = 1224444; for (int num : nums) { string s = to_string(num); if (s.size() < t.size()) continue; else if (s.size() > t.size()) { ans = min(ans, num); } else { // same length do { if (s > t) ans = min(ans, stoi(s)); } while (next_permutation(begin(s), end(s))); } } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment