Problem#
Count how many times the digit 2 appears in all non-negative integers from 0 to n inclusive.
Input: an integer n (assume n >= 0).
Output: an integer representing the total number of digit 2 occurrences in the range [0, n].
Examples#
Example 1#
1
2
3
Input: n = 20
Output: 3
Explanation: numbers with '2' are 2 , 12 , 20
Example 2#
1
2
Input: n = 22
Output: 6
Example 3#
1
2
Input: n = 100
Output: 20
Similar Problems
Solution#
Method 1 — Brute force#
Intuition#
Check every number from 0 to n and count how many 2 digits it contains.
Approach#
Initialize ans = 0.
For each i from 0 to n:
Convert or extract digits of i and count how many equal 2.
Add that count to ans.
Return ans.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public :
static long long count2s_bruteforce(long long n) {
long long ans = 0 ;
for (long long i = 0 ; i <= n; ++ i) {
long long x = i;
while (x > 0 ) {
if (x % 10 == 2 ) ++ ans;
x /= 10 ;
}
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
package main
func Count2sBrute (n int64 ) int64 {
var ans int64
for i := int64(0 ); i <= n ; i ++ {
x := i
for x > 0 {
if x % 10 == 2 { ans ++ }
x /= 10
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public static long count2sBrute (long n) {
long ans = 0;
for (long i = 0; i <= n; ++ i) {
long x = i;
while (x > 0) {
if (x % 10 == 2) ++ ans;
x /= 10;
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
object Solution {
fun count2sBrute (n: Long): Long {
var ans = 0L
var i = 0L
while (i <= n) {
var x = i
while (x > 0 ) {
if (x % 10 == 2L ) ans++
x /= 10
}
i++
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
class Solution :
def count2s_bruteforce (self, n: int) -> int:
ans = 0
for i in range(n + 1 ):
x = i
while x > 0 :
if x % 10 == 2 :
ans += 1
x //= 10
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
pub struct Solution ;
impl Solution {
pub fn count2s_bruteforce (n: i64 ) -> i64 {
let mut ans = 0 i64 ;
for i in 0 ..= n {
let mut x = i;
while x > 0 {
if x % 10 == 2 { ans += 1 }
x /= 10 ;
}
}
ans
}
}
Complexity#
⏰ Time complexity: O(n * log n) — we inspect each number up to n and examine its digits (≈ number of digits = O(log n)).
🧺 Space complexity: O(1) — constant extra space.
Method 2 — Place-value counting (positional contribution)#
Intuition#
For each decimal position (units, tens, hundreds…), compute how many times digit 2 appears at that position across [0, n] by analyzing higher digits, current digit, and lower digits.
For place value pow = 10^k, split n into higher = n // (pow*10), curr = (n // pow) % 10, and lower = n % pow. The contribution of this place to the total count is:
if curr < 2: higher * pow
if curr == 2: higher * pow + lower + 1
if curr > 2: (higher + 1) * pow
if curr > 2: (higher + 1) * pow
Sum contributions for all pow until pow > n.
Approach#
Initialize ans = 0 and pow = 1.
While pow <= n:
Compute higher = n // (pow*10).
Compute curr = (n // pow) % 10.
Compute lower = n % pow.
Add contribution according to curr as described above.
Multiply pow by 10 and repeat.
Return ans.
This runs in O(d) where d is the number of digits of n (≈ log10 n).
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public :
static long long count2s(long long n) {
long long ans = 0 ;
long long pow = 1 ;
while (pow <= n) {
long long higher = n / (pow * 10 );
long long curr = (n / pow) % 10 ;
long long lower = n % pow;
if (curr < 2 ) ans += higher * pow;
else if (curr == 2 ) ans += higher * pow + lower + 1 ;
else ans += (higher + 1 ) * pow;
pow *= 10 ;
}
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main
func Count2s (n int64 ) int64 {
var ans int64
var pow int64 = 1
for pow <= n {
higher := n / (pow * 10 )
curr := (n / pow ) % 10
lower := n % pow
if curr < 2 {
ans += higher * pow
} else if curr == 2 {
ans += higher * pow + lower + 1
} else {
ans += (higher + 1 ) * pow
}
pow *= 10
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public static long count2s (long n) {
long ans = 0;
long pow = 1;
while (pow <= n) {
long higher = n / (pow * 10);
long curr = (n / pow) % 10;
long lower = n % pow;
if (curr < 2) ans += higher * pow;
else if (curr == 2) ans += higher * pow + lower + 1;
else ans += (higher + 1) * pow;
pow *= 10;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
object Solution {
fun count2s (n: Long): Long {
var ans = 0L
var pow = 1L
while (pow <= n) {
val higher = n / (pow * 10 )
val curr = (n / pow) % 10
val lower = n % pow
ans += if (curr < 2 ) higher * pow
else if (curr == 2L ) higher * pow + lower + 1
else (higher + 1 ) * pow
pow *= 10
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution :
def count2s (self, n: int) -> int:
ans = 0
pow = 1
while pow <= n:
higher = n // (pow * 10 )
curr = (n // pow) % 10
lower = n % pow
if curr < 2 :
ans += higher * pow
elif curr == 2 :
ans += higher * pow + lower + 1
else :
ans += (higher + 1 ) * pow
pow *= 10
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pub struct Solution ;
impl Solution {
pub fn count2s (mut n: i64 ) -> i64 {
let mut ans = 0 i64 ;
let mut pow = 1 i64 ;
while pow <= n {
let higher = n / (pow * 10 );
let curr = (n / pow) % 10 ;
let lower = n % pow;
if curr < 2 { ans += higher * pow; }
else if curr == 2 { ans += higher * pow + lower + 1 ; }
else { ans += (higher + 1 ) * pow; }
pow *= 10 ;
}
ans
}
}
Complexity#
⏰ Time complexity: O(log n) — we iterate once per digit position (number of digits ≈ log10 n).
🧺 Space complexity: O(1) — constant extra space.