Count the Number of Powerful Integers | Digit DP | Hard Cases Problem

In this video, I'll talk about how to solve Leetcode Count the Number of Powerful Integers

Let's Connect:

About Me:
I am Aryan Mittal - A Software Engineer in Goldman Sachs, Speaker, Creator & Educator. During my free time, I create programming education content on this channel & also how to use that to grow :)

✨ Timelines✨

✨ Hashtags ✨
#programming #Interviews #leetcode #faang #maang #datastructures #algorithms

[moazgamal]

Very Helpful, Detailed, Clear, Excellent Explanation, Thank you.

[ARYANMITTAL]

Considering the number of solutions, this problem got, i don't think, this was that easy, that it got 500 AC's, May be Constraints are the cause of it 🥶

[SanjayKumar-iurq]

for num = 845, and limit = 6,
According to your code
for(int i=0;i<=ub && i<=limit;i++){
ans =


but for i==0,
ub = 8, and because of limit condition index will go to till 6 only,
so for 6, according to your explanation it should pass the tight =1 to next index,
but in your tight&(i==ub)
that wont be true brcause i==6 and ub==8 this will pass 0 to next iteration,
cn you please explain this part
}

[sukhpreetsingh]

4th que that suffix matching was quite diff

[phoddaal]

Bhaiya Leading Zeroes wali cheese isme kyon use Karne ki zarurat nahi ho rhi ?

[vanshbaghel]

Bro please don't use red color, it's not lesser visible than others 😁
Rest is good

It is not working for java code:

Code:
static long[][] dp = new long[20][2];

public static long numberOfPowerfulInt(long start, long finish, int limit, String s) {
String r = Long.toString(finish);
String l = Long.toString(start - 1);

for (long[] row: dp) Arrays.fill(row, -1);

long a = solve(r, s, 1, r.length(), limit);

for (long[] row: dp) Arrays.fill(row, -1);

long b = solve(l, s, 1, l.length(), limit);

return a - b;
}

private static long solve(String num, String s, int tight, int n, int limit) {
if (num.length() < s.length()) return 0;
if (dp[n][tight] != -1) return dp[n][tight];

// If tight hai, matlab if end is 3640 and current num is 3, then further nums cannot be greater than 640, else limit k upar hojayega, which will make it invalid. Therefore ub set krdo, ki iske upar nhi jaa skte, iske neeche hee raho.
int ub = tight == 1 ? num.charAt(num.length() - n) - '0' : limit;
long ans = 0;

// Matlab, last number of num hua, toh check with s
if (n == 1) {
// last char check karo
int lastCharOfS = s.charAt(s.length() - 1) - '0';

// Agar ub se greater hai apna nums ka last number, tab 0 return krdo. EG:
if (lastCharOfS > ub) return 0;
return 1;
}

// Means s se peeche k numbers hai, toh limit se chhota hona chahiye, buss itna dhyaan rakho
if (n <= s.length()) {
if (tight == 1) {
int correspondingSChar = s.charAt(s.length() - n) - '0';

if (correspondingSChar > ub) return 0;
else if (correspondingSChar == ub) {
ans = ans + solve(num, s, 1, n - 1, limit);
return ans;
// Means if corresponding s se smaller hai, ie,
} else return 1;
} else return 1;
} else {
for (int i = 0; i <= ub && i <= limit; i++) {
tight = tight == 1 & (i == ub) ? 1 : 0;
ans = ans + solve(num, s, tight, n - 1, limit);
}
}

return dp[n][tight] = ans;
}