algoadvance

Given two non-negative integers low and high, return the count of odd numbers between low and high (inclusive).

Clarifying Questions

Before we start implementing the solution, let’s clarify a few things:

  1. Are low and high always non-negative integers with 0 <= low <= high?
  2. Should the solution be optimized for large values of low and high?
  3. Are there any constraints on the size of low and high?

Let’s assume typical constraints (e.g., values less than (10^9)) and that low and high are valid as per the problem statement.

Strategy

To determine the count of odd numbers within the interval [low, high], we can follow this approach:

  1. Identify the properties of odd numbers:
    • An odd number is any number n such that n % 2 != 0.
  2. Range properties:
    • If low is odd, include it; otherwise, consider the next number (if within bounds).
    • Similarly, if high is odd, include it; otherwise, consider the preceding number (if within bounds).
  3. Mathematical deduction:
    • Count odd numbers from 1 to high.
    • Count odd numbers from 1 to low-1.
    • The difference between these two counts gives us the number of odd numbers between low and high.

Given x, the number of odd numbers from 1 to x is (x + 1) // 2.

Code

Here’s the implementation of the above strategy:

def count_odds(low: int, high: int) -> int:
    def count_odds_up_to(x: int) -> int:
        return (x + 1) // 2
    
    return count_odds_up_to(high) - count_odds_up_to(low - 1)

# Example usage
low = 3
high = 7
print(count_odds(low, high))  # Output: 3 (numbers are 3, 5, 7)

Time Complexity

The time complexity of this solution is (O(1)) as it involves a fixed amount of arithmetic operations irrespective of the input size.

Using this efficient mathematical approach ensures that the solution works optimally even for large values of low and high.

Try our interview co-pilot at AlgoAdvance.com