Count Evenly Good Integers Python solution?

In Python, convert the upper bound to a string to get its digits, then define a recursive function with @lru_cache over (position, summary, tight). Iterate over digits 0 to 9, respect the upper bound when tight is true, and update the summary for each choice. Subtract the count for L - 1 from the count for R to get the range answer.

Is Count Evenly Good Integers easy or hard?

It is rated Hard on FleetCode, with an acceptance rate of about 79.6 percent. The difficulty comes from designing the digit DP state correctly rather than from the code itself. Once the state is clear, the implementation is a standard memoized recursion.

How to solve Count Evenly Good Integers in O(log N)?

Use digit DP. The number of digits is log10(N), so the position dimension is O(log N), and the transitions per state are constant (at most 10 digit choices). The total work is O(log N * S), where S is the size of the summary state. Memoization ensures each (position, summary, tight) combination is computed only once.

What is the best approach for Count Evenly Good Integers?

Digit DP is the best approach. It processes the number digit by digit, tracks a tight-bound flag and a compact summary of the digits seen so far, and memoizes each state. This runs in O(d * S * 10) time, where d is the digit count and S is the number of summary states, which stays fast even for bounds near 10^18.

What data structure is used in Count Evenly Good Integers?

The main structure is a memoization table, usually a multidimensional array indexed by digit position, summary state, and tight flag, or a hash map keyed by those values. Digits are extracted from the bound with integer division and modulo by 10, so no string or list is strictly required.

What is the time complexity of Count Evenly Good Integers?

The optimal digit DP solution runs in O(d * S * 10) time, where d is the number of digits in the bound and S is the number of distinct summary states. The brute force enumeration runs in O(N * d) time, where N is the size of the range, which is too slow for large inputs.

Is Count Evenly Good Integers asked at Google, Amazon, or Meta?

The FleetCode listing tags this problem under General and does not list specific company associations. Digit DP problems appear regularly in interviews at large tech companies, so practicing the pattern is useful regardless of which company you target.

Description Solution

4060. Count Evenly Good Integers

Hard77.8% acceptancePremium elsewhere, free here

You are given two integers l and r.

An integer is called evenly good if it contains an even number of even digits.

Return the number of evenly good integers in the inclusive range [l, r].

Example 1:

Input: l = 18, r = 22

Output: 3

Explanation:

The evenly good integers in the range [18, 22] are:

19, because it contains 0 even digits.
20, because it contains 2 even digits.
22, because it contains 2 even digits.

Thus, the answer is 3.

Example 2:

Input: l = 98, r = 101

Output: 2

Explanation:

The evenly good integers in the range [98, 101] are:

99, because it contains 0 even digits.
100, because it contains 2 even digits.

Thus, the answer is 2.

Example 3:

Input: l = 1, r = 10

Output: 5

Explanation:

The evenly good integers in the range [1, 10] are 1, 3, 5, 7, and 9, because each of them contains 0 even digits. Thus, the answer is 5.

Constraints:

1 <= l <= r <= 10¹⁵

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

No sample inputs for this problem yet. The examples in the statement show the format.

Your code is saved on this device.Solution