Count the number of 2s between 0 and n

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

Input: n = 20
Output: 3
Explanation: numbers with '2' are 2, 12, 20

Example 2

Input: n = 22
Output: 6

Example 3

Input: n = 100
Output: 20

Solution

Method 1 — Brute force

Intuition

Check every number from 0 to n and count how many 2 digits it contains.

Approach

1. Initialize ans = 0.
2. For each i from 0 to n:
   • Convert or extract digits of i and count how many equal 2.
   • Add that count to ans.
3. Return ans.

Code

C++

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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

pub struct Solution;
impl Solution {
    pub fn count2s_bruteforce(n: i64) -> i64 {
        let mut ans = 0i64;
        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

1. Initialize ans = 0 and pow = 1.
2. 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.
3. Return ans.

This runs in O(d) where d is the number of digits of n (≈ log10 n).

Code

C++

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;
    }
};

Go

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
}

Java

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;
    }
}

Kotlin

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
    }
}

Python

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

Rust

pub struct Solution;
impl Solution {
    pub fn count2s(mut n: i64) -> i64 {
        let mut ans = 0i64;
        let mut pow = 1i64;
        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.