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.
1def countDigitOne(n: int) -> int:
2 count = 0
3 for i in range(1, n + 1):
4 count += str(i).count('1')
5 return count
6
7n = 13
8print(countDigitOne(n))This Python code converts each number to a string and uses the count method to find occurrences of '1'.
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.
1public
This Java solution counts 1s at each digit level using arithmetic and logical checks, efficiently counting occurrences of the digit 1.