Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2048.html

2048. Next Greater Numerically Balanced Number (Medium)

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 1. Brute Force

• // OJ: https://leetcode.com/problems/next-greater-numerically-balanced-number/
// Time: O(C * logC) where C is the maximum possible input number.
// Space: O(1)
class Solution {
bool balance(int n) {
int cnt[10] = {};
while (n) {
if (n % 10 == 0) return false; // no 0 allowed
cnt[n % 10]++;
n /= 10;
}
for (int i = 1; i < 10; ++i) {
if (cnt[i] && cnt[i] != i) return false;
}
return true;
}
public:
int nextBeautifulNumber(int n) {
while (true) {
++n;
if (balance(n)) return n;
}
}
};

• class Solution:
def nextBeautifulNumber(self, n: int) -> int:
def check(num):
counter = [0] * 10
for c in str(num):
counter[int(c)] += 1

for c in str(num):
if counter[int(c)] != int(c):
return False
return True

for i in range(n + 1, 10**7):
if check(i):
return i
return -1

############

# 2048. Next Greater Numerically Balanced Number
# https://leetcode.com/problems/next-greater-numerically-balanced-number

class Solution:
def nextBeautifulNumber(self, n: int) -> int:
n += 1
c = Counter(str(n))

def good(c):
for k, v in c.items():
if int(k) != v:
return False

return True

while not good(c):
n += 1
c = Counter(str(n))

return n


• class Solution {
public int nextBeautifulNumber(int n) {
for (int i = n + 1; i < 10000000; ++i) {
if (check(i)) {
return i;
}
}
return -1;
}

private boolean check(int num) {
int[] counter = new int[10];
char[] chars = String.valueOf(num).toCharArray();
for (char c : chars) {
++counter[c - '0'];
}
for (char c : chars) {
if (counter[c - '0'] != c - '0') {
return false;
}
}
return true;
}
}

• func nextBeautifulNumber(n int) int {
check := func(num int) bool {
s := strconv.Itoa(num)
counter := make([]int, 10)
for _, c := range s {
counter[int(c-'0')]++
}
for _, c := range s {
if counter[int(c-'0')] != int(c-'0') {
return false
}
}
return true
}

for i := n + 1; i <= 10000000; i++ {
if check(i) {
return i
}
}
return -1
}

• function nextBeautifulNumber(n: number): number {
for (let ans = n + 1; ; ans++) {
if (isValid(ans)) {
return ans;
}
}
}

function isValid(n: number): boolean {
let record = new Array(10).fill(0);
while (n > 0) {
const idx = n % 10;
record[idx]++;
n = Math.floor(n / 10);
}
for (let i = 0; i < 10; i++) {
if (record[i] && record[i] != i) return false;
}
return true;
}



Discuss

https://leetcode.com/problems/next-greater-numerically-balanced-number/discuss/1537491/C%2B%2B-Brute-Force