# Java/Python one pass solution easy to understand

• The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

``````if n = xyzdabc
``````

and we are considering the occurrence of one on thousand, it should be:

``````(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1
``````

iterate through all digits and sum them all will give the final answer

Java

``````public int countDigitOne(int n) {

if (n <= 0) return 0;
int q = n, x = 1, ans = 0;
do {
int digit = q % 10;
q /= 10;
ans += q * x;
if (digit == 1) ans += n % x + 1;
if (digit >  1) ans += x;
x *= 10;
} while (q > 0);
return ans;

}

// 40 / 40 test cases passed.
// Status: Accepted
// Runtime: 0 ms
``````

Python

``````def countDigitOne(self, n):
if n <= 0:
return 0
q, x, ans = n, 1, 0
while q > 0:
digit = q % 10
q /= 10
ans += q * x
if digit == 1:
ans += n % x + 1
elif digit > 1:
ans += x
x *= 10
return ans

# 40 / 40 test cases passed.
# Status: Accepted
# Runtime: 32 ms
# 97.59%``````

• This solution is great!

• I would really appreciate if someone can explain how/why does this work.

• this solution is much easier to be understood! thank you!

• This explanation is clear, thanks!

• For me this is the best explanation and implementation

• Great, Thanks for your sharing.

• Spent quite sometime trying to figure out why we should do a n/m + 8.......
Yours is much easier to understand! Thanks!

• I don't understand the algorithm , can you please explain it ?
Thank you

• For people who doesn't understand the author's explanations, just look at some examples:

Let n = 4560000

How many nums with "1" at the thousand's position?

4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)

That's 456 * 1000

What if n = 4561234?

4561000-4561234 (1234+1)
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)

That's 456 * 1000 + 1234 + 1

What if n = 4562345?
4561000-4561999 (1000)
4551000 to 4551999 (1000)
4541000 to 4541999 (1000)
4531000 to 4531999 (1000)
...
1000 to 1999 (1000)

That's 456*1000 + 1000

Same for hundred's position.

Let n = 4012

How many nums with "1" at the hundred's position?

3100-3999 (100)
2100-2999 (100)
1100-1999 (100)
100 to 199 (100)
That's 4 * 100

Let n = 4111

4100-4111 ( 11 + 1)
3100-3999 (100)
2100-2999 (100)
1100-1999 (100)
100 to 199 (100)
That's 4 * 100 + 11 + 1

Let n = 4211

4100-4199 (100)
3100-3999 (100)
2100-2999 (100)
1100-1999 (100)
100 to 199 (100)
That's 4 * 100 + 100

Same for ten's digit

Let n = 30
How many nums with "1" at the ten's position?

210-219 (10)
110-119 (10)
10-19 (10)

That's 3 * 10

Let n = 312

310-312 (2 + 1)
210-219 (10)
110-119 (10)
10-19 (10)
That's 3 * 10 + 2 + 1

Let n = 322

310-319 (10)
210-219 (10)
110-119 (10)
10-19 (10)
That's 3 * 10 + 10

Same for one's digit

Let n = 30
How many nums with "1" at the one's position?

21 (1)
11 (1)
1(1)
That's 3 * 1

Let n = 31
How many "1" are there at the one's position?
31 (1)
21 (1)
11 (1)
1 (1)
That's 3 * 1 + 1

Let n = 32
How many "1" are there at the one's position?
31 (10)
21 (10)
11 (10)
1 (10)
That's 3 * 1 + 1

Let n = 3

only 1 (10 of "1" at one's position)

That's 0 * 1 + 1

• ``````The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

if n = xyzdabc
and we are considering the occurrence of one on thousand, it should be:

(1) xyz * 1000 + 0                    if d == 0, means there is no 1 because of  this digit(none)
(2) xyz * 1000 + abc + 1          if d == 1, means there is abc of  1 because  of this digit(patrial)
(3) xyz * 1000 + 1000              if d > 1,  means there  is fully 1000 of  1 because of  this digit(fully)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.