gpt-4o-2024-08-06· OpenAI
WildChat-4.8M (AI2)
Give simple, common, and optimised Java solution Given an integer n, count the total…
- User
Give simple, common, and optimised Java solution
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. Example 1: Input: n = 13 Output: 6 Example 2: Input: n = 0 Output: 0 Constraints: • 0 <= n <= 109 class Solution { public int countDigitone (int n) { 3 5
- Assistant
Here is a simple and efficient Java solution to count the total number of digit 1 appearing in all non-negative integers less than or equal to
n:class Solution { public int countDigitOne(int n) { int count = 0; long factor = 1; // Start with the least significant digit while (n / factor > 0) { long lowerNumbers = n - (n / factor) * factor; long currentDigit = (n / factor) % 10; long higherNumbers = n / (factor * 10); // Count 1s contributed by the current digit if (currentDigit == 0) { count += higherNumbers * factor; } else if (currentDigit == 1) { count += higherNumbers * factor + (lowerNumbers + 1); } else { count += (higherNumbers + 1) * factor; } // Move to the next significant digit factor *= 10; } return count; } }Explanation:
-
Variables and Initialization:
countkeeps track of the total number of ones counted.factoris used to iterate over each digit position (units, tens, hundreds, etc.).
-
Loop Through Each Digit:
lowerNumberscalculates the number of numbers less than the current position.currentDigitextracts the digit at the current position.higherNumberscalculates the number of numbers greater than the current position.
-
Counting Ones:
- If
currentDigitis 0, then the digit 1 appearshigherNumbers * factortimes. - If
currentDigitis 1, then the digit 1 appearshigherNumbers * factor + (lowerNumbers + 1)times. - If
currentDigitis greater than 1, then the digit 1 appears(higherNumbers + 1) * factortimes.
- If
-
Update Factor:
- Multiply
factorby 10 to move to the next significant digit.
- Multiply
This approach efficiently calculates the number of times digit 1 appears across increasing powers of ten, thereby optimizing the count with O(log n) complexity.
-