# 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.

O(1)