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.
1#
The C code iterates over each digit position and calculates how often a 1 would appear at that position using arithmetic based on the surrounding digits. The core idea is to count 1s in each digit position separately.