Daily Leetcode - Next Greater Numerically Balanced Number
1. Thinking Process
1.1. ✅ Observation 1
Valid digits are 1–6 only.
Because any digit ≥7 would require ≥7 copies → the number exceeds 10⁶ quickly.
1.2. ✅ Observation 2
Each valid balanced number is formed by choosing a subset of digits from {1,2,3,4,5,6} and repeating each digit exactly that many times.
Example:
{1} → 1
{2} → 22
{1,3} → 1333 (all permutations of 1 and 333)
{2,3} → 22333, 23323, etc.
1.3. ✅ Observation 3
We only need to test all possible balanced numbers until we find one > n.
1.3. Dry run sample:
digits used pattern length example
{1} 1 1
{2} 2 22
{1,2} 3 122, 212, 221
{3} 3 333
{1,3} 4 1333
{1,2,3} 6 122333
... ... ...
{1,2,3,4,5,6} 21 122333444455555666666
mask subset generated number comment
000001 {1} 1 small
000010 {2} 22 small
000011 {1,2} 122 medium
000100 {3} 333 medium
000101 {1,3} 1333 medium
001001 {1,4} 14444 large
001111 {1,2,3,4} 1223334444 huge
2. Code Walkthrough
2.1. Permutation All Solution
from itertools import permutations
class Solution:
def nextBeautifulNumber(self, n: int) -> int:
digits = ['1', '2', '3', '4', '5', '6']
best = float('inf')
for mask in range(1, 1 << 6): # all subsets of digits {1..6}
s = ""
for i, d in enumerate(digits):
if (mask >> i) & 1:
s += d * int(d) # e.g. for 3 → add '333'
# Generate all permutations of the string
for p in set(permutations(s)): # remove duplicates
val = int(''.join(p))
if val > n:
best = min(best, val)
return best
-
Time: O(21!) worst case — huge → TLE.
-
Space: O(k!) for storing permutations.
2.2. Naive Solution (O(range * n))
class Solution:
def isBalanced(self, x: int) -> bool:
count = {}
for c in str(x):
count[c] = count.get(c, 0) + 1
for d, freq in count.items():
if int(d) != freq:
return False
return True
def nextBeautifulNumber(self, n: int) -> int:
num = n + 1
while True:
if self.isBalanced(num):
return num
num += 1
-
Suppose result = m.
-
Check every number from n+1 → m, each check costs O(d) (number of digits).
-
Time: O(m − n) ≈ O(range × digits).
-
Space: O(1).
2.3. Optimize Solution
from itertools import permutations
class Solution:
def nextBeautifulNumber(self, n: int) -> int:
digits = ['1', '2', '3', '4', '5', '6']
best = float('inf')
for mask in range(1, 1 << 6): # all subsets of {1..6}
s = ""
for i, d in enumerate(digits):
if (mask >> i) & 1:
s += d * int(d)
# Skip if even the largest permutation <= n
if int(''.join(sorted(s, reverse=True))) <= n:
continue
# Permute lexicographically (smallest → largest)
for p in permutations(sorted(s)):
val = int(''.join(p))
if val > n:
best = min(best, val)
break # stop for this subset once found
return best
-
Skip subsets whose max permutation ≤ n (prune).
-
Constant total subsets (63) and digits (≤ 21).
3. Intuitive
3.1. Order of the larger subset must be after the previous small number
mask (binary) digits included subset
000001 {1} '1'
000010 {2} '2'
000011 {1,2} '1','2'
000100 {3} '3'
000101 {1,3} '1','3'
000110 {2,3} '2','3'
000111 {1,2,3} '1','2','3'
001000 {4} '4'
001001 {1,4} '1','4'
001010 {2,4} '2','4'
3.2. Do not make sure the next subset larger than previous subset
🧩 Step 1. What the bitmask order guarantees
The bitmask order (binary counting) does not guarantee numeric order of the generated numbers.
Example: mask subset smallest balanced number 000011 {1,2} 122 000100 {3} 333
Here:
{1,2} comes before {3} in bitmask order ✅
But 333 > 122 — so yes, “next subset” gives larger number.
✅ This one happens to be true, but…
⚠️ Step 2. But it’s not always true globally
Let’s compare {2,3} vs {4}:
subset balanced pattern smallest value {2,3} 22333 22,333 {4} 4444 4,444