# Count Odd Numbers in an Interval Range
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-odd-numbers-in-an-interval-range)
Canonical: https://scaleengineer.com/dsa/problems/count-odd-numbers-in-an-interval-range
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
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^9`

# Approaches
## Brute Force Iteration
This approach involves iterating through each number in the given range from `low` to `high`. For each number, we perform a check to see if it is odd. A counter is maintained to keep track of the total count of odd numbers found.
**Time:** O(high - low). The time taken is directly proportional to the size of the interval. For large ranges (up to 10^9 as per constraints), this approach will be too slow and result in a Time Limit Exceeded (TLE) error. · **Space:** O(1). We only use a constant amount of extra memory for the counter and loop variable, regardless of the input range size.
**Pros:** Very simple to understand and implement.; Works correctly for small ranges.
**Cons:** Highly inefficient for large ranges.; Will not pass the time constraints on most competitive programming platforms for this problem due to the large constraints (up to 10^9).
### Explanation
The algorithm is very straightforward:

*   Initialize a counter variable, `count`, to zero.
*   Create a loop that iterates from `low` to `high`, inclusive.
*   Inside the loop, for each number `i`, use the modulo operator (`%`) to check if it's odd (`i % 2 != 0`).
*   If the number is odd, increment the `count`.
*   After the loop completes, the `count` variable will hold the total number of odd integers in the range, which is then returned.

Here is the Java implementation:
```java
class Solution {
    public int countOdds(int low, int high) {
        int count = 0;
        for (int i = low; i <= high; i++) {
            if (i % 2 != 0) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter variable `count` to 0.
*   Loop through each integer `i` from `low` to `high` (inclusive).
*   Inside the loop, check if `i` is odd using the modulo operator (`i % 2 != 0`).
*   If `i` is odd, increment `count`.
*   After the loop finishes, return `count`.

## Constant Time Mathematical Approach
A much more efficient approach is to use a mathematical formula to calculate the result in constant time, avoiding any loops. The core idea is to find the count of odd numbers from 0 up to `high` and subtract the count of odd numbers from 0 up to `low - 1`.
**Time:** O(1). The solution consists of a fixed number of arithmetic operations. The execution time is constant and does not depend on the values of `low` and `high`. · **Space:** O(1). No extra space is allocated that scales with the input size.
**Pros:** Extremely efficient and fast.; Optimal solution for this problem.; Handles the entire range of constraints (up to 10^9) without any issues.
**Cons:** Requires some mathematical insight to derive the formula, making it slightly less intuitive than the brute-force method.
### Explanation
The number of positive odd integers less than or equal to a given non-negative integer `n` can be calculated with a simple formula: `count = (n + 1) / 2`. This works due to integer division.

For example:
*   Odd numbers up to 7: [1, 3, 5, 7]. Count = 4. `(7 + 1) / 2 = 4`.
*   Odd numbers up to 8: [1, 3, 5, 7]. Count = 4. `(8 + 1) / 2 = 9 / 2 = 4`.

To find the number of odd numbers in the range `[low, high]`, we can apply this logic:

*   Calculate the number of odd integers from 0 up to `high`. Let's call this `oddsUpToHigh`. Using our formula, `oddsUpToHigh = (high + 1) / 2`.
*   Calculate the number of odd integers from 0 up to `low - 1`. Let's call this `oddsUpToLowMinus1`. Using our formula, `oddsUpToLowMinus1 = ((low - 1) + 1) / 2 = low / 2`.
*   The result is the difference between these two counts: `oddsUpToHigh - oddsUpToLowMinus1`.

This method performs a few simple arithmetic operations and returns the result instantly, regardless of the size of the range.

Here is the Java implementation:
```java
class Solution {
    public int countOdds(int low, int high) {
        // Count of odd numbers up to high is (high + 1) / 2
        // Count of odd numbers up to low - 1 is low / 2
        return (high + 1) / 2 - low / 2;
    }
}
```
### Algorithm
*   Calculate the count of odd numbers from 0 to `high`: `countHigh = (high + 1) / 2`.
*   Calculate the count of odd numbers from 0 to `low - 1`: `countLow = low / 2`.
*   The result is the difference: `countHigh - countLow`.
*   Return the result.

# Solutions
### Java

```java
class Solution { public int countOdds ( int low , int high ) { return (( high + 1 ) >> 1 ) - ( low >> 1 ); } }
```

### CPP

```cpp
class Solution { public: int countOdds ( int low , int high ) { return ( high + 1 >> 1 ) - ( low >> 1 ); } };
```

### Python

```python
class Solution : def countOdds ( self , low : int , high : int ) -> int : return (( high + 1 ) >> 1 ) - ( low >> 1 )
```