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.
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.