1523. Count Odd Numbers in an Interval Range

[mah-shamim]

Topics: Math, Biweekly Contest 31

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

Example 1:

• Input: low = 3, high = 7
• Output: 3
• Explanation: The odd numbers between 3 and 7 are [3,5,7].

Example 2:

• Input: low = 8, high = 10
• Output: 1
• Explanation: The odd numbers between 8 and 10 are [9].

Constraints:

• 0 <= low <= high <= 10⁹

Hint:

1. If the range (high - low + 1) is even, the number of even and odd numbers in this range will be the same.
2. If the range (high - low + 1) is odd, the solution will depend on the parity of high and low.

[mah-shamim]

We are given two non-negative integers low and high. We need to count the number of odd numbers between low and high (inclusive).

The straightforward way is to iterate from low to high and count the odd numbers. However, this would be O(n) and might be too slow for large inputs (up to 10⁹). Therefore, we need a mathematical approach.

Approach:

• Calculate the number of odd numbers from 0 to high using integer division: (high + 1) // 2
• Calculate the number of odd numbers from 0 to low - 1 using integer division: low // 2
• Subtract the second result from the first to get the count of odd numbers in the range [low, high]

Let's implement this solution in PHP: 1523. Count Odd Numbers in an Interval Range

<?php
/**
 * @param Integer $low
 * @param Integer $high
 * @return Integer
 */
function countOdds($low, $high) {
    // Count odds from 0 to high minus odds from 0 to low-1
    $countToHigh = (int)(($high + 1) / 2);
    $countToLowMinusOne = (int)($low / 2);

    return $countToHigh - $countToLowMinusOne;
}

// Test cases
echo countOdds(3, 7) . "\n";        // Output: 3
echo countOdds(8, 10) . "\n";       // Output: 1
?>

Explanation:

• The number of odd numbers from 0 to any non-negative integer n is (n + 1) // 2 (integer division)
• For example, from 0 to 7: odd numbers are [1,3,5,7] → (7+1)//2 = 4
• The count of odd numbers in [low, high] equals the count in [0, high] minus the count in [0, low-1]
• This gives us: ((high + 1) // 2) - (low // 2)
• This formula handles all cases correctly, including when low = 0 or when low = high

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

[kovatz]

Thanks for solving the problem of "Count Odd Numbers in an Interval Range"

[mah-shamim]

Thanks