class Solution {
public String smallestNumber(String num, long t) {
Pair<Map<Integer, Integer>, Boolean> primeCountResult = getPrimeCount(t);
Map<Integer, Integer> primeCount = primeCountResult.getKey();
boolean isDivisible = primeCountResult.getValue();
if (!isDivisible)
return "-1";
Map<Integer, Integer> factorCount = getFactorCount(primeCount);
if (sumValues(factorCount) > num.length())
return construct(factorCount);
Map<Integer, Integer> primeCountPrefix = getPrimeCount(num);
int firstZeroIndex = num.indexOf('0');
if (firstZeroIndex == -1) {
firstZeroIndex = num.length();
if (isSubset(primeCount, primeCountPrefix))
return num;
}
for (int i = num.length() - 1; i >= 0; --i) {
final int d = num.charAt(i) - '0';
// Remove the current digit's factors from primeCountPrefix.
primeCountPrefix = subtract(primeCountPrefix, FACTOR_COUNTS.get(d));
final int spaceAfterThisDigit = num.length() - 1 - i;
if (i > firstZeroIndex)
continue;
for (int biggerDigit = d + 1; biggerDigit < 10; ++biggerDigit) {
// Compute the required factors after replacing with a larger digit.
Map<Integer, Integer> factorsAfterReplacement = getFactorCount(
subtract(subtract(primeCount, primeCountPrefix), FACTOR_COUNTS.get(biggerDigit)));
// Check if the replacement is possible within the available space.
if (sumValues(factorsAfterReplacement) <= spaceAfterThisDigit) {
// Fill extra space with '1', if any, and construct the result.
final int fillOnes = spaceAfterThisDigit - sumValues(factorsAfterReplacement);
return num.substring(0, i) + // Keep the prefix unchanged.
biggerDigit + // Replace the current digit.
"1".repeat(fillOnes) + // Fill remaining space with '1'.
construct(factorsAfterReplacement);
}
}
}
// No solution of the same length exists, so we need to extend the number
// by prepending '1's and adding the required factors.
Map<Integer, Integer> factorsAfterExtension = getFactorCount(primeCount);
return "1".repeat(num.length() + 1 - sumValues(factorsAfterExtension)) +
construct(factorsAfterExtension);
}
private static final Map<Integer, Map<Integer, Integer>> FACTOR_COUNTS = Map.of(
0, Map.of(), 1, Map.of(), 2, Map.of(2, 1), 3, Map.of(3, 1), 4, Map.of(2, 2), 5, Map.of(5, 1),
6, Map.of(2, 1, 3, 1), 7, Map.of(7, 1), 8, Map.of(2, 3), 9, Map.of(3, 2));
// Returns the prime count of t and if t is divisible by 2, 3, 5, 7.
private Pair<Map<Integer, Integer>, Boolean> getPrimeCount(long t) {
Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
for (int prime : new int[] {2, 3, 5, 7}) {
while (t % prime == 0) {
t /= prime;
count.put(prime, count.get(prime) + 1);
}
}
return new Pair<>(count, t == 1);
}
// Returns the prime count of `num`.
private Map<Integer, Integer> getPrimeCount(String num) {
Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
for (final char c : num.toCharArray()) {
Map<Integer, Integer> digitFactors = FACTOR_COUNTS.get(c - '0');
for (Map.Entry<Integer, Integer> entry : digitFactors.entrySet()) {
final int prime = entry.getKey();
final int freq = entry.getValue();
count.merge(prime, freq, Integer::sum);
}
}
return count;
}
private Map<Integer, Integer> getFactorCount(Map<Integer, Integer> count) {
// 2^3 = 8
final int count8 = count.get(2) / 3;
final int remaining2 = count.get(2) % 3;
// 3^2 = 9
final int count9 = count.get(3) / 2;
int count3 = count.get(3) % 2;
// 2^2 = 4
int count4 = remaining2 / 2;
int count2 = remaining2 % 2;
// Combine 2 and 3 to 6 if both are present
int count6 = 0;
if (count2 == 1 && count3 == 1) {
count2 = 0;
count3 = 0;
count6 = 1;
}
// Combine 3 and 4 to 2 and 6 if both are present
if (count3 == 1 && count4 == 1) {
count2 = 1;
count6 = 1;
count3 = 0;
count4 = 0;
}
return Map.of(2, count2, 3, count3, 4, count4, 5, count.get(5), 6, count6, 7, count.get(7), 8,
count8, 9, count9);
}
private String construct(Map<Integer, Integer> factors) {
StringBuilder sb = new StringBuilder();
for (int digit = 2; digit < 10; ++digit)
sb.append(String.valueOf(digit).repeat(factors.get(digit)));
return sb.toString();
}
// Returns true if a is a subset of b.
private boolean isSubset(Map<Integer, Integer> a, Map<Integer, Integer> b) {
for (Map.Entry<Integer, Integer> entry : a.entrySet())
if (b.get(entry.getKey()) < entry.getValue())
return false;
return true;
}
// Returns a - b.
private Map<Integer, Integer> subtract(Map<Integer, Integer> a, Map<Integer, Integer> b) {
Map<Integer, Integer> res = new HashMap<>(a);
for (Map.Entry<Integer, Integer> entry : b.entrySet()) {
final int key = entry.getKey();
final int value = entry.getValue();
res.put(key, Math.max(0, res.get(key) - value));
}
return res;
}
// Returns the sum of the values in `count`.
private int sumValues(Map<Integer, Integer> count) {
return count.values().stream().mapToInt(Integer::intValue).sum();
}
}
FACTOR_COUNTS = {
0: collections.Counter(),
1: collections.Counter(),
2: collections.Counter([2]),
3: collections.Counter([3]),
4: collections.Counter([2, 2]),
5: collections.Counter([5]),
6: collections.Counter([2, 3]),
7: collections.Counter([7]),
8: collections.Counter([2, 2, 2]),
9: collections.Counter([3, 3]),
}
class Solution:
def smallestNumber(self, num: str, t: int) -> str:
primeCount, isDivisible = self._getPrimeCount(t)
if not isDivisible:
return '-1'
factorCount = self._getFactorCount(primeCount)
if sum(factorCount.values()) > len(num):
return ''.join(factor * freq for factor, freq in factorCount.items())
primeCountPrefix = sum((FACTOR_COUNTS[int(c)]
for c in num), start=collections.Counter())
firstZeroIndex = next((i for i, d in enumerate(num) if d == '0'), len(num))
if firstZeroIndex == len(num) and primeCount <= primeCountPrefix:
return num
for i, c in reversed(list(enumerate(num))):
d = int(c)
# Remove the current digit's factors from primeCountPrefix.
primeCountPrefix -= FACTOR_COUNTS[d]
spaceAfterThisDigit = len(num) - 1 - i
if i <= firstZeroIndex:
for biggerDigit in range(d + 1, 10):
# Compute the required factors after replacing with a larger digit.
factorsAfterReplacement = self._getFactorCount(
primeCount - primeCountPrefix - FACTOR_COUNTS[biggerDigit]
)
# Check if the replacement is possible within the available space.
if sum(factorsAfterReplacement.values()) <= spaceAfterThisDigit:
# Fill extra space with '1', if any, and construct the result.
fillOnes = spaceAfterThisDigit - sum(
factorsAfterReplacement.values())
return (
num[:i] # Keep the prefix unchanged.
+ str(biggerDigit) # Replace the current digit.
+ '1' * fillOnes # Fill remaining space with '1'.
+ ''.join(factor * freq for factor,
freq in factorsAfterReplacement.items())
)
# No solution of the same length exists, so we need to extend the number
# by prepending '1's and adding the required factors.
factorCount = self._getFactorCount(primeCount)
return (
'1' * (len(num) + 1 - sum(factorCount.values()))
+ ''.join(factor * freq for factor, freq in factorCount.items())
)
def _getPrimeCount(self, t: int) -> tuple[dict[int, int], bool]:
"""
Returns the count of prime factors of t and if t is divisible by 2, 3, 5, 7.
"""
count = collections.Counter()
for prime in [2, 3, 5, 7]:
while t % prime == 0:
t //= prime
count[prime] += 1
return count, t == 1
def _getFactorCount(self, count: dict[int, int]) -> dict[str, int]:
"""Returns the required factors to form the smallest number."""
count8, remaining2 = divmod(count[2], 3) # 2^3 = 8
count9, count3 = divmod(count[3], 2) # 3^2 = 9
count4, count2 = divmod(remaining2, 2) # 2^2 = 4
# Combine 2 and 3 to 6 if both are present.
count2, count3, count6 = ((0, 0, 1) if count2 == 1 and count3 == 1
else (count2, count3, 0))
# Combine 3 and 4 to 2 and 6 if both are present.
count2, count6, count3, count4 = ((1, 1, 0, 0)
if count3 == 1 and count4 == 1
else (count2, count6, count3, count4))
return {'2': count2, '3': count3, '4': count4, '5': count[5],
'6': count6, '7': count[7], '8': count8, '9': count9}
class Solution {
public:
string smallestNumber(string num, long long t) {
const auto [primeCount, isDivisible] = getPrimeCount(t);
if (!isDivisible)
return "-1";
const unordered_map<int, int> factorCount = getFactorCount(primeCount);
if (sumValues(factorCount) > num.length())
return consturct(factorCount);
unordered_map<int, int> primeCountPrefix = getPrimeCount(num);
int firstZeroIndex = num.find('0');
if (firstZeroIndex == string::npos) {
firstZeroIndex = num.length();
if (isSubset(primeCount, primeCountPrefix))
return num;
}
for (int i = num.length() - 1; i >= 0; --i) {
const int d = num[i] - '0';
// Remove the current digit's factors from primeCountPrefix.
primeCountPrefix = substract(primeCountPrefix, kFactorCounts.at(d));
const int spaceAfterThisDigit = num.length() - 1 - i;
if (i > firstZeroIndex)
continue;
for (int biggerDigit = d + 1; biggerDigit < 10; ++biggerDigit) {
// Compute the required factors after replacing with a larger digit.
const unordered_map<int, int> factorsAfterReplacement =
getFactorCount(substract(substract(primeCount, primeCountPrefix),
kFactorCounts.at(biggerDigit)));
// Check if the replacement is possible within the available space.
if (sumValues(factorsAfterReplacement) <= spaceAfterThisDigit) {
// Fill extra space with '1', if any, and construct the result.
const int fillOnes =
spaceAfterThisDigit - sumValues(factorsAfterReplacement);
return num.substr(0, i) + // Keep the prefix unchanged.
to_string(biggerDigit) + // Replace the current digit.
string(fillOnes, '1') + // Fill remaining space with '1'.
consturct(factorsAfterReplacement);
}
}
}
// No solution of the same length exists, so we need to extend the number
// by prepending '1's and adding the required factors.
const unordered_map<int, int> factorsAfterExtension =
getFactorCount(primeCount);
return string(num.length() + 1 - sumValues(factorsAfterExtension), '1') +
consturct(factorsAfterExtension);
}
private:
constexpr static unordered_map<int, unordered_map<int, int>> kFactorCounts = {
{0, {}}, {1, {}}, {2, {{2, 1}}}, {3, {{3, 1}}},
{4, {{2, 2}}}, {5, {{5, 1}}}, {6, {{2, 1}, {3, 1}}}, {7, {{7, 1}}},
{8, {{2, 3}}}, {9, {{3, 2}}}};
// Returns the prime count of t and if t is divisible by 2, 3, 5, 7.
pair<unordered_map<int, int>, bool> getPrimeCount(long t) {
unordered_map<int, int> count{{2, 0}, {3, 0}, {5, 0}, {7, 0}};
for (const int prime : {2, 3, 5, 7}) {
while (t % prime == 0) {
t /= prime;
++count[prime];
}
}
return {count, t == 1};
}
// Returns the prime count of `num`.
unordered_map<int, int> getPrimeCount(const string& num) {
unordered_map<int, int> count{{2, 0}, {3, 0}, {5, 0}, {7, 0}};
for (const char d : num)
for (const auto& [prime, freq] : kFactorCounts.at(d - '0'))
count[prime] += freq;
return count;
}
unordered_map<int, int> getFactorCount(const unordered_map<int, int>& count) {
unordered_map<int, int> res;
// 2^3 = 8
const int count8 = count.at(2) / 3;
const int remaining2 = count.at(2) % 3;
// 3^2 = 9
const int count9 = count.at(3) / 2;
int count3 = count.at(3) % 2;
// 2^2 = 4
int count4 = remaining2 / 2;
int count2 = remaining2 % 2;
// Combine 2 and 3 to 6 if both are present.
int count6 = 0;
if (count2 == 1 && count3 == 1) {
count2 = 0;
count3 = 0;
count6 = 1;
}
// Combine 3 and 4 to 2 and 6 if both are present.
if (count3 == 1 && count4 == 1) {
count2 = 1;
count6 = 1;
count3 = 0;
count4 = 0;
}
return unordered_map<int, int>{
{2, count2}, {3, count3}, {4, count4}, {5, count.at(5)},
{6, count6}, {7, count.at(7)}, {8, count8}, {9, count9}};
}
string consturct(const unordered_map<int, int>& factors) {
string res;
for (int digit = 2; digit < 10; ++digit)
res += string(factors.at(digit), '0' + digit);
return res;
}
// Returns true if a is a subset of b.
bool isSubset(const unordered_map<int, int>& a,
const unordered_map<int, int>& b) {
for (const auto& [key, value] : a)
if (b.at(key) < value)
return false;
return true;
}
// Returns a - b.
unordered_map<int, int> substract(unordered_map<int, int> a,
const unordered_map<int, int>& b) {
for (const auto& [key, value] : b)
a[key] = max(0, a[key] - value);
return a;
}
// Returns the sum of the values in `count`.
int sumValues(const unordered_map<int, int>& count) {
return accumulate(
count.begin(), count.end(), 0,
[](int acc, const pair<int, int>& p) { return acc + p.second; });
}
};
const FACTOR = {
0:{},1:{},2:{2:1},3:{3:1},4:{2:2},
5:{5:1},6:{2:1,3:1},7:{7:1},
8:{2:3},9:{3:2}
};
var smallestNumber = function(num, t) {
const [prime, ok] = getPrimeCountT(t);
if (!ok) return "-1";
let factor = getFactorCount(prime);
if (sumValues(factor) > num.length)
return construct(factor);
let prefix = getPrimeCountNum(num);
let firstZero = num.indexOf('0');
if (firstZero === -1) {
firstZero = num.length;
if (isSubset(prime, prefix))
return num;
}
for (let i = num.length - 1; i >= 0; i--) {
let d = Number(num[i]);
prefix = subtract(prefix, FACTOR[d]);
let space = num.length - 1 - i;
if (i > firstZero) continue;
for (let bigger = d + 1; bigger <= 9; bigger++) {
let need = getFactorCount(
subtract(
subtract(prime, prefix),
FACTOR[bigger]
)
);
if (sumValues(need) <= space) {
return num.slice(0, i)
+ bigger
+ "1".repeat(space - sumValues(need))
+ construct(need);
}
}
}
let need = getFactorCount(prime);
return "1".repeat(num.length + 1 - sumValues(need))
+ construct(need);
};
function getPrimeCountT(t){
let cnt={2:0,3:0,5:0,7:0};
for(let p of [2,3,5,7]){
while(t%p===0){
cnt[p]++;
t/=p;
}
}
return [cnt,t===1];
}
function getPrimeCountNum(num){
let cnt={2:0,3:0,5:0,7:0};
for(let ch of num){
for(let p in FACTOR[ch]){
cnt[p]+=FACTOR[ch][p];
}
}
return cnt;
}
function getFactorCount(c){
let c8=Math.floor(c[2]/3), rem2=c[2]%3;
let c9=Math.floor(c[3]/2), c3=c[3]%2;
let c4=Math.floor(rem2/2), c2=rem2%2, c6=0;
if(c2&&c3){ c2=0;c3=0;c6=1; }
if(c3&&c4){ c2=1;c6=1;c3=0;c4=0; }
return {2:c2,3:c3,4:c4,5:c[5],6:c6,7:c[7],8:c8,9:c9};
}
function construct(f){
let s="";
for(let d=2;d<=9;d++)
s+=String(d).repeat(f[d]);
return s;
}
function isSubset(a,b){
for(let p in a)
if(b[p]<a[p]) return false;
return true;
}
function subtract(a,b){
let r={...a};
for(let p in b)
r[p]=Math.max(0,r[p]-b[p]);
return r;
}
function sumValues(mp){
return Object.values(mp).reduce((x,y)=>x+y,0);
}