algoadvance

Leetcode 2180. Count Integers With Even Digit Sum

Problem Statement

Given a positive integer num, return the number of positive integers less than or equal to num whose digit sums are even.

Clarifying Questions

1. Q: What are the constraints on the value of num?
   • A: num is a positive integer, typically within the range of 1 to 10^5.
2. Q: Do we consider 0 as an even digit sum?
   • A: Yes, since 0 is even.
3. Q: Should negative numbers or non-integer inputs be considered?
   • A: No, the input num will always be a positive integer as per the problem statement.

Strategy

1. Convert Integer to Digits: For each integer i from 1 to num, compute the sum of its digits.
2. Check if Even: Check if the digit sum is even.
3. Count the Valid Numbers: Maintain a counter to keep track of how many numbers satisfy the condition of having an even digit sum.

The solution involves iterating through all numbers from 1 to num and calculating the digit sum. This approach can be optimized further, but for simplicity, we’ll start with a direct implementation.

Code Implementation

public class Solution {
    public int countEven(int num) {
        int count = 0;
        
        for (int i = 1; i <= num; i++) {
            if (isEvenDigitSum(i)) {
                count++;
            }
        }
        
        return count;
    }
    
    private boolean isEvenDigitSum(int n) {
        int sum = 0;
        
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        
        return sum % 2 == 0;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countEven(30)); // Example test case
    }
}

Time Complexity

• Iterating through the Numbers: We need to consider each number from 1 to num, which takes O(num) time.
• Calculating Digit Sum: For each number i, calculating the digit sum involves summing up its digits, which takes O(d) time, where d is the number of digits in i. In the worst case, the number of digits can be approximately log10(num). Hence, for each check, it takes around O(log num).

Thus, the overall time complexity is O(num * log num), because for every number from 1 to num, we are performing an operation that takes O(log num) time.

Conclusion

The provided solution iterates through each number up to num, calculates the sum of the digits, and checks if the sum is even, counting the occurrences of such numbers. It’s a straightforward approach with a clear time complexity of O(num * log num). This should be efficient enough for typical constraint limits as mentioned in the problem statement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?