Number of Digit One

This page explains Java solution to problem Number of Digit One using Math.

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: 13
Output: 6

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

class NumberOfDigitOne {
    public int countDigitOne(int n) {
        /**
             let's say number is 13

             Now at Unit place digit 1 appears 2 times in 1, 11

                 Unit place so pow = 1
                    quotient  = 13 / 10 = 1
                    remainder = 13 % 10 = 3

                 count += quotient * pow
                    count += 1 * 1
                    count = 1

                 count += Math.min(pow, remainder - pow + 1)
                    count += Math.min(1, 3 - 1 + 1) = 1
                    count  = 2

             Now at Tenth place digit 1 appear 4 times in 10, 11, 12, 13

                 Tenth place so pow = 10
                    quotient = 13 / 100 = 0
                    remainder = 13 % 100 = 13

                 count += quotient * pow
                    count += 0 * 10
                    count = 2

                 count += Math.min(pow, remainder - pow + 1)
                    count += Math.min(10, 13 - 10 + 1) = 4
                    count = 6
        */
        int count = 0;
        for(long pow = 1; pow <= n; pow *= 10) {
            long divisor = pow * 10;

            long quotient = n / divisor;
            long remainder = n % divisor;

            count += quotient * pow;
            if(remainder >= pow) {
                count += Math.min(pow, remainder - pow + 1);
            }
        }
        return count;
    }
}

Time Complexity

O(log10(N)) Where
No of iterations equal to the number of digits in input number N.

Space Complexity

O(1)