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: Can num be zero?
    • A: No, num is a positive integer.
  2. Q: Should the numbers be inclusive of num?
    • A: Yes, we need to consider integers from 1 to num inclusive.
  3. Q: What would be a large value for num?
    • A: The value of num is within the constraints as specified in the problem, typically meaning it can be up to (10^6).

Strategy

To solve this problem, we need to count how many integers between 1 and num have an even digit sum. We will do the following:

  1. Iterate from 1 to num.
  2. For each integer, calculate the sum of its digits.
  3. Check if the sum is even.
  4. Increment a counter if the digit sum is even.
  5. Return the counter at the end.

We’ll need a helper function to compute the sum of digits of a number. Our main function can then use this helper function to determine if the digit sum is even and keep track of the count of such integers.

Code

Here is the C++ code to solve the problem:

#include <iostream>

class Solution {
public:
    int countEven(int num) {
        int evenCount = 0;
        
        for (int i = 1; i <= num; ++i) {
            if (isEvenDigitSum(i)) {
                ++evenCount;
            }
        }
        return evenCount;
    }

private:
    bool isEvenDigitSum(int number) {
        int sum = 0;
        while (number > 0) {
            sum += number % 10;
            number /= 10;
        }
        return sum % 2 == 0;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     int num = 30;
//     std::cout << "Count of integers with even digit sum up to " << num << " is: " << sol.countEven(num) << std::endl;
//     return 0;
// }

Time Complexity

The time complexity of this solution is (O(n \log n)):

Thus, the overall time complexity is (O(n \log n)). This solution is efficient enough for the typical constraint (1 \leq num \leq 10^6).

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