The digit product of any number only ever carries the primes 2, 3, 5, and 7, so before touching `num` I factor `t` into `2^a * 3^b * 5^c * 7^d`. If anything is left over — a stray 11 or 13 — no product of digits `1`-`9` can supply it, and the answer is `-1` outright. The tempting approach is to start at `num` and count upward, testing each candidate's digit product. That works for the small "I" variant, but here `num` reaches `2*10^5` digits and the target can sit astronomically far above it, so incrementing one integer at a time never finishes. Instead I build the answer directly: keep the longest prefix of `num` I can, raise one digit by the minimum, then fill the remaining tail with the cheapest digits that still supply every missing prime. Digits `5` and `7` are the only sources of a 5 or a 7, so those counts are forced; a small DP over the needed powers of 2 and 3 finds the fewest digits to cover them, and everything else becomes a `1` to keep the number small. If no same-length answer clears `num`, I grow to one more digit and emit the smallest valid number of that length. ### Worked example Take `num = "1234"`, `t = 256 = 2^8`, so I need eight factors of 2 and nothing else. Keeping the whole `"1234"` gives product `1*2*3*4 = 24 = 2^3 * 3` — only three 2s, short. I keep the prefix `"1"`, raise the `2` at index 1 to `4` (that is `2^2`), which leaves `2^6` for the two trailing slots. Two `8`s give `2^3` each, so the tail is `"88"` and the result is `"1488"`, with digit product `1*4*8*8 = 256`. Raising an earlier digit, or this one to something smaller, either misses the 2s or yields a larger number. ### Complexity - Time O(n) — one linear pass over `num` builds the prefix exponent sums, and each of the `n` branch positions does O(1) work against a DP table whose size (powers of 2 and 3, both under 47) is fixed by `t <= 10^14`. - Space O(n) — four prefix-exponent arrays over the digits of `num`; the DP table itself is constant-sized. ### Code (C++) ```cpp #include using namespace std; static const int E2[10]={0,0,1,0,2,0,1,0,3,0}; static const int E3[10]={0,0,0,1,0,0,1,0,0,2}; static const int E5[10]={0,0,0,0,0,1,0,0,0,0}; static const int E7[10]={0,0,0,0,0,0,0,1,0,0}; class Solution { public: int A,B; vector> cnt; vector> seqs; string ins(const string&s, char c){ string r=s; r.push_back(c); sort(r.begin(), r.end()); return r; } void buildDP(){ cnt.assign(A+1, vector(B+1, INT_MAX)); seqs.assign(A+1, vector(B+1, string())); cnt[0][0]=0; seqs[0][0]=""; int opt[6]={2,3,4,6,8,9}; for(int i=0;i<=A;i++) for(int j=0;j<=B;j++){ if(i==0&&j==0) continue; for(int k=0;k<6;k++){ int d=opt[k]; int pi=max(0,i-E2[d]), pj=max(0,j-E3[d]); if(cnt[pi][pj]==INT_MAX) continue; int nc=cnt[pi][pj]+1; string ns=ins(seqs[pi][pj],'0'+d); if(nc p2(n+1,0),p3(n+1,0),p5(n+1,0),p7(n+1,0); int firstZero=n; for(int i=0;i=a && p3[n]>=b && p5[n]>=c && p7[n]>=d) return num; } int hi = min(n-1, firstZero); for(int i=hi;i>=0;i--){ int px2=p2[i],px3=p3[i],px5=p5[i],px7=p7[i]; int cur=num[i]-'0'; int sufLen=n-1-i; for(int dd=cur+1;dd<=9;dd++){ int r2=max(0,a-px2-E2[dd]); int r3=max(0,b-px3-E3[dd]); int r5=max(0,c-px5-E5[dd]); int r7=max(0,d-px7-E7[dd]); if(minNon(r2,r3,r5,r7)<=sufLen){ string suf=build(sufLen,r2,r3,r5,r7); return num.substr(0,i) + char('0'+dd) + suf; } } } int need = minNon(a,b,c,d); int L = max(n+1, need); return build(L,a,b,c,d); } }; ``` ### One note Track exponents, never the product. The digits of `num` can multiply to a value with `2*10^5` digits — no integer type holds that — but the exponent of any single prime tops out around `6*10^5` (all `8`s), which sits comfortably in an `int`. The other trap is the forced `5`s and `7`s: because only the digits `5` and `7` carry those primes, a target like `125 = 5^3` demands three literal `5`s, so `"99"` has to grow to `"555"` even though it gains a digit. When a factor comes from exactly one digit, its required count is a hard floor on the length — check that floor before assuming a same-length answer exists.