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.
1public class Main {
2 public static int countDigitOne(int n) {
3 int count = 0;
4 for (int i = 1; i <= n; i++) {
5 int num = i;
6 while (num > 0) {
7 if (num % 10 == 1) count++;
8 num /= 10;
9 }
10 }
11 return count;
12 }
13
14 public static void main(String[] args) {
15 int n = 13;
16 System.out.println(countDigitOne(n));
17 }
18}This Java code uses the same logic as the C/C++ code. For each number from 1 to n, it checks each digit and counts the occurrence of 1s.
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
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.