Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-08-06· OpenAIAi2 WildChat-4.8M (AI2)

Give simple, common, and optimised Java solution Given an integer n, count the total…

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

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

      • count keeps track of the total number of ones counted.
      • factor is used to iterate over each digit position (units, tens, hundreds, etc.).
    • Loop Through Each Digit:

      • lowerNumbers calculates the number of numbers less than the current position.
      • currentDigit extracts the digit at the current position.
      • higherNumbers calculates the number of numbers greater than the current position.
    • Counting Ones:

      • If currentDigit is 0, then the digit 1 appears higherNumbers * factor times.
      • If currentDigit is 1, then the digit 1 appears higherNumbers * factor + (lowerNumbers + 1) times.
      • If currentDigit is greater than 1, then the digit 1 appears (higherNumbers + 1) * factor times.
    • Update Factor:

      • Multiply factor by 10 to move to the next significant digit.

    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.