Problem Link :https://www.geeksforgeeks.org/problems/count-numbers-containing-43022/1
Problem Description : You are given a number n, Return the count of total numbers from 1 to n containing 4 as a digit.
Examples:
Input: n = 9 Output: 1 Explanation: 4 is the only number between 1 to 9 which contains 4 as a digit. Input: n = 44 Output: 9 Explanation: 4, 14, 24, 34, 40, 41, 42, 43 & 44, there are total 9 numbers containing 4 as a digit.
At first 0 to 9 only one four will be there , so let's keep it as base case
Next level is 100
100 made up of 10 tens
So each ten may contribute 1 that is previous level answer
But 40-49 contribute 10 numbers So for 100 it's 4(0 to 3 )×1 + 10 + 4(5 to 9)×1 So for 1-100 it's 19
If we take 1000 , 1000 made of 10 100s Each 100 gives 19 , 400-499 gives 100 So for 0 to 1000 4×19 + 100+ 5×19
Now I can find this , but if number was not perfect 10 power number say it's 76 ,now I will find upto 100 need to cut down the remaining 24 values contribution
Here's my approach , can somebody help me finish that
class Solution {
public static int countNumberswith4(int n) {
int decimalPower = (int) Math.log10(n) + 1;
int[] dp = new int[decimalPower];
dp[0] = 1;
for (int i = 1; i < decimalPower; i++) {
dp[i] = 4 * dp[i - 1] + (int) Math.pow(10, i) + 5 * dp[i - 1];
}
int result = dp[decimalPower - 1];
int diff = (int) Math.pow(10, decimalPower) - n;
System.out.println(result+" "+diff);
int i = 0;
while(diff>0){
int curr = diff%10;
if(curr>)
}
return result;
}
}
I tried by taking digits from the difference between the nearest greater 10 power and n to reduce the unwanted contribution ?
