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.
1def countDigitOne
In this Python solution, for each digit in n, the number of occurrences of '1' at that digit position is calculated and aggregated to provide the final count.