Sponsored
Sponsored
In this approach, we iterate through each number from 0 to n. For each number, we count the number of times digit 1 appears. Although this approach is simple, it's not optimal for large values of n due to its high time complexity.
Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n.
Space Complexity: O(1), as it uses a fixed amount of space.
1using System;
2
3class Program {
4 static int CountDigitOne(int n) {
5 int count = 0;
6 for (int i = 1; i <= n; i++) {
7 int num = i;
8 while (num > 0) {
9 if (num % 10 == 1) count++;
10 num /= 10;
11 }
12 }
13 return count;
14 }
15
16 static void Main() {
17 int n = 13;
18 Console.WriteLine(CountDigitOne(n));
19 }
20}This C# code implements the same logic as the C/C++ code, iterating over each number and checking its digits.
This optimized approach examines digit positions and calculates how many times 1 appears at each position up to n. It leverages the structure of numbers and is more efficient for large values of n.
Time Complexity: O(log10(n)), as it iterates digit by digit.
Space Complexity: O(1), as it uses a fixed amount of space.
1using System;
2
class Program {
static int CountDigitOne(int n) {
int count = 0;
for (long i = 1; i <= n; i *= 10) {
long divider = i * 10;
count += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i);
}
return count;
}
static void Main() {
int n = 13;
Console.WriteLine(CountDigitOne(n));
}
}This C# solution applies the same systematic counting of 1s per digit position by leveraging modulus and division operations.