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.
1#include <stdio.h>
2
3int countDigitOne(int n) {
4 int count = 0;
5 for (int i = 1; i <= n; i++) {
6 int num = i;
7 while (num > 0) {
8 if (num % 10 == 1) count++;
9 num /= 10;
10 }
11 }
12 return count;
13}
14
15int main() {
16 int n = 13;
17 printf("%d\n", countDigitOne(n));
18 return 0;
19}The code iterates from 1 to n and for each number, it counts the number of the digit 1 by repeatedly dividing the number by 10 and checking the remainder. It increments count each time a 1 is found.
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.
1#include <iostream>
2using namespace std;
int countDigitOne(int n) {
int count = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
count += (n / divider) * i + ((n % divider >= i) ? (n % divider - i + 1) : 0);
}
return count;
}
int main() {
int n = 13;
cout << countDigitOne(n) << endl;
return 0;
}Similar to the C solution, the C++ solution uses mathematical operations to determine the count of digit 1s by handling each digit position.