analyze each digit position separately. for position i (from right), count how many times 1 appears at that position. depends on the digit at position i and digits to its left and right.
formula: for digit d at position i, count depends on higher digits (determines cycles), current digit (determines partial cycle), and lower digits (determines position in cycle).
approach
- process each digit position from right to left
- calculate contributions from higher, current, and lower digits
- sum contributions from all positions
complexity
O(log n) time to process each digit position. O(1) space. efficient mathematical solution.