We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Digit One

Number: 233

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, Amazon, Salesforce, Uber

Problem Description

Count the total number of digit 1 appearing in all non-negative integers less than or equal to a given integer n.

Key Insights

  • Analyze each digit position in n (ones, tens, hundreds, etc.) independently.
  • For each digit position, decompose n into three parts: high (digits left of the current position), current (the digit at the current position), and low (digits right of the current position).
  • Depending on the value of the current digit:
    • If it is 0, its contribution is solely defined by the higher digits.
    • If it is 1, count both the higher digits and the remainder (low) plus one.
    • If it is greater than 1, the contribution is fully determined by the higher digits incremented by one.
  • This mathematical method avoids inefficient iterations and leverages place value analysis.

Space and Time Complexity

Time Complexity: O(log n) because the number of digits in n determines the loop iterations. Space Complexity: O(1) as only a few integer variables are used.

Solution

We use a mathematical approach by iterating over each digit position. At each position, calculate:

  • high: n divided by the current digit place multiplied by 10.
  • current: the digit at the current position from n.
  • low: the remainder when n is divided by the current digit place. Based on the value of the current digit, determine its contribution to the total count of 1's using specific formulae:
  • If current == 0: add high * i.
  • If current == 1: add high * i + (low + 1).
  • Else: add (high + 1) * i. This algorithm efficiently counts the digit 1 occurrences without iterating through every number from 0 to n.

Code Solutions

# Python solution for counting the number of digit one in range [0, n]

def countDigitOne(n: int) -> int:
    count = 0
    i = 1  # digit position (1, 10, 100, ...)
    while i <= n:
        # Divide n into parts based on the current digit's place value.
        divider = i * 10
        high = n // divider  # higher part of n
        current = (n // i) % 10  # digit at current position
        low = n % i  # lower part of n
        
        # Accumulate count from high digits contributions.
        if current == 0:
            count += high * i
        elif current == 1:
            count += high * i + low + 1
        else:
            count += (high + 1) * i
        
        # Move to the next position.
        i *= 10
        
    return count

# Example usage:
print(countDigitOne(13))  # Output: 6
← Back to All Questions