30 Jun 2024•PHP•Hard

Number of Digit One

count total number of digit 1 appearing in all numbers from 1 to n using digit dp or mathematical analysis.

View original LeetCode question

analyze each digit position separately. for position i (from right), count how many times 1 appears at that position. depends on the digit at position i and digits to its left and right.

formula: for digit d at position i, count depends on higher digits (determines cycles), current digit (determines partial cycle), and lower digits (determines position in cycle).

approach

  • process each digit position from right to left
  • calculate contributions from higher, current, and lower digits
  • sum contributions from all positions

complexity

O(log n) time to process each digit position. O(1) space. efficient mathematical solution.

Solution files

PHP•number-of-digit-one/solution.php
class Solution {

function countDigitOne($n) {
    if ($n < class="syntax-number">0) return class="syntax-number">0;
    
    $count = class="syntax-number">0;
    $factor = class="syntax-number">1;
    $n_copy = $n;
    
    while ($n_copy > class="syntax-number">0) {
        $digit = $n_copy % class="syntax-number">10;
        $higher = intval($n_copy / class="syntax-number">10);
        $lower = $n % $factor;
        
        $count += $higher * $factor;
        
        if ($digit > class="syntax-number">1) {
            $count += $factor;
        } elseif ($digit == class="syntax-number">1) {
            $count += $lower + class="syntax-number">1;
        }
        
        $factor *= class="syntax-number">10;
        $n_copy = intval($n_copy / class="syntax-number">10);
    }
    
    return $count;
}
}

$solution = new Solution();
echo $solution->countDigitOne(class="syntax-number">13);
echo $solution->countDigitOne(class="syntax-number">0);