cppAcademy
FROM LEARNING TO COMPETING

Intermediate.
Put your skills to the test.

Bulgarian Informatics Group D · 2007–2026

270 independently explained problems: 54 Municipal, 54 Regional, 105 National Olympiad and 57 Autumn Tournament tasks. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group D also includes challenging national-level problems. The six 2017 National tasks shared by Groups C and D use their existing permanent URLs. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP D2015 · MediumPositional digit counting

Count One Digit from Zero to n

National Olympiad — Regional round (2015 season)

Submission name: digits.cpp

Solve in Editor →

Problem summary

Count every occurrence of decimal digit k in the ordinary representations of all integers from 0 through n, including both endpoints and the single representation 0.

Input

k n.

Output

The total number of occurrences.

Constraints

0 ≤ k ≤ 9; 0 < n ≤ 10^18.

Worked example

Input and output for the worked example discussed below.

Input

3 42

Output

14

Solution analysis

  1. Count one decimal position at a time: units, tens, hundreds, and so on. For place value f, split n into higher=n/(10f), current=(n/f) mod 10, and lower=n mod f. Each complete cycle contributes higher×f copies of a nonzero target digit.
  2. For nonzero k, the incomplete final cycle contributes f if current>k, lower+1 if current=k, and nothing otherwise. Sum these contributions over every place f≤n.
  3. Zero needs separate handling because leading zeros are not written. When higher>0, use (higher−1)f instead of higher×f, then add f or lower+1 according to current. Add one at the start for the number 0 itself.
  4. For digit 3 up to 42, the units place contributes four occurrences in 3,13,23,33. The tens place contributes ten in 30…39. The total is 14. Number 33 correctly contributes twice.

Why it works

For a fixed position the decimal representations cycle in blocks of 10f; each nonzero digit occupies exactly f numbers in a complete block, and the final partial block has the stated size. Removing the first zero block excludes all leading zeros. Each written digit belongs to exactly one position, so summing position counts gives the total.

Complexity: O(log10 n) time and O(1) auxiliary space. The count fits signed 64-bit for n≤10^18. Compute higher as n/f/10 to avoid forming an overflowing 10f.

Watch out. Count 0 itself once when k=0, exclude leading zeros, and include n. Avoid floating-point powers and avoid multiplying the final place by 10.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    int target;
    long long n;
    cin>>target>>n;
    long long answer=target==0?1:0;
    for(long long place=1;place<=n;){
        long long higher=n/place/10;
        int current=int(n/place%10);
        long long lower=n%place;
        if(target!=0){
            answer+=higher*place;
            if(current>target){
                answer+=place;
            }
            else if(current==target){
                answer+=lower+1;
            }
        }
        else if(higher>0){
            // Remove the cycle that would write a leading zero.
            answer+=(higher-1)*place;
            answer+=current==0?lower+1:place;
        }
        if(place>n/10){
            break;
        }
        place*=10;
    }
    cout<<answer<<'\n';
}

Source: Arena Olimpiici ↗