Welcome to Subscribe On Youtube

1067. Digit Count in Range

Description

Given a single-digit integer d and two integers low and high, return the number of times that d occurs as a digit in all integers in the inclusive range [low, high].

 

Example 1:

Input: d = 1, low = 1, high = 13
Output: 6
Explanation: The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13.
Note that the digit d = 1 occurs twice in the number 11.

Example 2:

Input: d = 3, low = 100, high = 250
Output: 35
Explanation: The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.

 

Constraints:

  • 0 <= d <= 9
  • 1 <= low <= high <= 2 * 108

Solutions

  • class Solution {
        private int d;
        private int[] a = new int[11];
        private int[][] dp = new int[11][11];
    
        public int digitsCount(int d, int low, int high) {
            this.d = d;
            return f(high) - f(low - 1);
        }
    
        private int f(int n) {
            for (var e : dp) {
                Arrays.fill(e, -1);
            }
            int len = 0;
            while (n > 0) {
                a[++len] = n % 10;
                n /= 10;
            }
            return dfs(len, 0, true, true);
        }
    
        private int dfs(int pos, int cnt, boolean lead, boolean limit) {
            if (pos <= 0) {
                return cnt;
            }
            if (!lead && !limit && dp[pos][cnt] != -1) {
                return dp[pos][cnt];
            }
            int up = limit ? a[pos] : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (i == 0 && lead) {
                    ans += dfs(pos - 1, cnt, lead, limit && i == up);
                } else {
                    ans += dfs(pos - 1, cnt + (i == d ? 1 : 0), false, limit && i == up);
                }
            }
            if (!lead && !limit) {
                dp[pos][cnt] = ans;
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        int d;
        int a[11];
        int dp[11][11];
    
        int digitsCount(int d, int low, int high) {
            this->d = d;
            return f(high) - f(low - 1);
        }
    
        int f(int n) {
            memset(dp, -1, sizeof dp);
            int len = 0;
            while (n) {
                a[++len] = n % 10;
                n /= 10;
            }
            return dfs(len, 0, true, true);
        }
    
        int dfs(int pos, int cnt, bool lead, bool limit) {
            if (pos <= 0) {
                return cnt;
            }
            if (!lead && !limit && dp[pos][cnt] != -1) {
                return dp[pos][cnt];
            }
            int up = limit ? a[pos] : 9;
            int ans = 0;
            for (int i = 0; i <= up; ++i) {
                if (i == 0 && lead) {
                    ans += dfs(pos - 1, cnt, lead, limit && i == up);
                } else {
                    ans += dfs(pos - 1, cnt + (i == d), false, limit && i == up);
                }
            }
            if (!lead && !limit) {
                dp[pos][cnt] = ans;
            }
            return ans;
        }
    };
    
  • class Solution:
        def digitsCount(self, d: int, low: int, high: int) -> int:
            return self.f(high, d) - self.f(low - 1, d)
    
        def f(self, n, d):
            @cache
            def dfs(pos, cnt, lead, limit):
                if pos <= 0:
                    return cnt
                up = a[pos] if limit else 9
                ans = 0
                for i in range(up + 1):
                    if i == 0 and lead:
                        ans += dfs(pos - 1, cnt, lead, limit and i == up)
                    else:
                        ans += dfs(pos - 1, cnt + (i == d), False, limit and i == up)
                return ans
    
            a = [0] * 11
            l = 0
            while n:
                l += 1
                a[l] = n % 10
                n //= 10
            return dfs(l, 0, True, True)
    
    
  • func digitsCount(d int, low int, high int) int {
    	f := func(n int) int {
    		a := make([]int, 11)
    		dp := make([][]int, 11)
    		for i := range dp {
    			dp[i] = make([]int, 11)
    			for j := range dp[i] {
    				dp[i][j] = -1
    			}
    		}
    		l := 0
    		for n > 0 {
    			l++
    			a[l] = n % 10
    			n /= 10
    		}
    
    		var dfs func(int, int, bool, bool) int
    		dfs = func(pos, cnt int, lead, limit bool) int {
    			if pos <= 0 {
    				return cnt
    			}
    			if !lead && !limit && dp[pos][cnt] != -1 {
    				return dp[pos][cnt]
    			}
    			up := 9
    			if limit {
    				up = a[pos]
    			}
    			ans := 0
    			for i := 0; i <= up; i++ {
    				if i == 0 && lead {
    					ans += dfs(pos-1, cnt, lead, limit && i == up)
    				} else {
    					t := cnt
    					if d == i {
    						t++
    					}
    					ans += dfs(pos-1, t, false, limit && i == up)
    				}
    			}
    			if !lead && !limit {
    				dp[pos][cnt] = ans
    			}
    			return ans
    		}
    
    		return dfs(l, 0, true, true)
    	}
    	return f(high) - f(low-1)
    }
    

All Problems

All Solutions