Count Odd Numbers in an Interval Range

Count Odd Numbers in an Interval Range

What is this problem about?

In this "Easy" coding problem, you are given two non-negative integers, low and high. Your task is to count how many odd numbers exist in the inclusive range $[low, high]$.

Why is this asked in interviews?

Companies like Microsoft and Google use this as a very basic "sanity check" or a warm-up question. It tests whether a candidate can think mathematically and avoid an $O(n)$ loop. In programming interviews, even simple problems often have an $O(1)$ solution that interviewers expect you to find.

Algorithmic pattern used

The pattern is Simple Math / Parity Logic. Instead of iterating through the range, you can calculate the count using the formula: (high + 1) / 2 - low / 2. Alternatively, you can find the number of integers in the range ($high - low + 1$) and adjust based on whether the boundaries are odd or even.

Example explanation

Range: [3, 7]

• Naive: 3, 5, 7. Count = 3.
• Math:
  • Total numbers up to 7 that are odd: (7 + 1) / 2 = 4 (1, 3, 5, 7).
  • Total numbers up to 2 (one less than low) that are odd: (2 + 1) / 2 = 1 (1).
  • Count in range = 4 - 1 = 3.

Common mistakes candidates make

The most common mistake is using a loop to count the numbers, which is unnecessary and inefficient for large ranges (e.g., $0$ to $10^9$). Another mistake is incorrect integer division or "off-by-one" errors when applying the mathematical formula.

Interview preparation tip

Always look for $O(1)$ solutions for problems involving ranges and counts. If the property you are counting (like being odd) alternates perfectly, there is almost always a formulaic way to find the answer.