Last updated on January 18th, 2025 at 09:56 pm

Here, we see a Number of Digit One LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Math

Level of Question

Hard

Number of Digit One LeetCode Solution

1. Problem Statement

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:
Input: n = 13
Output: 6

Example 2:
Input: n = 0
Output: 0

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Mathematical Digit Manipulation”. This pattern involves breaking down a number into its individual digits and performing calculations based on their positions and values.

3. Code Implementation in Different Languages

3.1 Number of Digit One C++

class Solution { 
public:
    int countDigitOne(int n) {
    int ret = 0;
      for(long long int i = 1; i <= n; i*= (long long int)10){
         int a = n / i;
         int b = n % i;
         int x = a % 10;
         if(x ==1){
            ret += (a / 10) * i + (b + 1);
         }
         else if(x == 0){
            ret += (a / 10) * i;
         } else {
            ret += (a / 10 + 1) *i;
         }
      }
      return ret;
    }
};

3.2 Number of Digit One Java

class Solution {
  public int countDigitOne(int n) {
    int ans = 0;
    for (long pow10 = 1; pow10 <= n; pow10 *= 10) {
      final long divisor = pow10 * 10;
      final int quotient = (int) (n / divisor);
      final int remainder = (int) (n % divisor);
      if (quotient > 0)
        ans += quotient * pow10;
      if (remainder >= pow10)
        ans += Math.min(remainder - pow10 + 1, pow10);
    }
    return ans;
  }
}

3.3 Number of Digit One JavaScript

var countDigitOne = function(n) {
    if(n <= 0) return 0;
    if(n < 10) return 1;
    var base = Math.pow(10, n.toString().length - 1);
    var answer = parseInt(n / base);
    return countDigitOne(base - 1) * answer + (answer === 1 ? (n - base + 1) : base) + countDigitOne(n % base);
};

3.4 Number of Digit One Python

class Solution(object):
    def countDigitOne(self, n):
        ones, m = 0, 1
        while m <= n:
            ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1)
            m *= 10
        return ones

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log₁₀(n))	O(1)
Java	O(log₁₀(n))	O(1)
JavaScript	O(log₁₀(n))	O(log₁₀(n))
Python	O(log₁₀(n))	O(1)

• The time complexity is logarithmic because the algorithm processes each digit position in the number n.
• The space complexity is constant for C++, Java, and Python because no additional data structures are used. However, JavaScript uses recursion, which adds a logarithmic space complexity due to the recursion stack.
• The mathematical digit manipulation pattern is efficient for problems involving digit-based calculations.