We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Odd Numbers in an Interval Range

Number: 1630

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

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

Key Insights

  • The range is inclusive of both endpoints.
  • Instead of iterating through the range, we can use mathematical properties of integers.
  • Half of the integers up to any number are odd. Use integer division to count odds.
  • Compute the odds up to high and subtract the odds up to (low - 1).

Space and Time Complexity

Time Complexity: O(1) Space Complexity: O(1)

Solution

The idea is to count the number of odd numbers from 1 to high and subtract the number of odd numbers from 1 to (low - 1). The formula to count odd numbers up to a given number n is n // 2 if n is even, and (n // 2 + 1) if n is odd. This can be simplified into a single formula: (n + 1) // 2. So, the result is given by (high + 1) // 2 - (low) // 2.

  • Data Structures Used: Only integers and arithmetic operations.
  • Algorithmic Approach: Mathematical formula based on integer division. No iteration over the range.
  • Mental Leap: Realizing that calculating odds up to a number allows direct computation avoiding explicit loop iteration, making it efficient.

Code Solutions

# Python code to count odd numbers in an inclusive range

def count_odds(low, high):
    # Calculate the number of odd numbers from 1 to high
    odds_up_to_high = (high + 1) // 2
    # Calculate the number of odd numbers from 1 to (low - 1)
    odds_up_to_low_minus_one = low // 2
    # The difference gives the number of odds between low and high (inclusive)
    return odds_up_to_high - odds_up_to_low_minus_one

# Example usage
if __name__ == "__main__":
    low = 3
    high = 7
    print("Output:", count_odds(low, high))  # Expected Output: 3
← Back to All Questions