Skip to main content

Count Odd Numbers in an Interval Range

Problem Description​

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

Examples​

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

Solution for Counting Odd Numbers in an Interval Range​

Brute Force Approach​

The brute force approach involves iterating through each number between low and high and counting how many of these numbers are odd.

Code in Different Languages​

Written by @ImmidiSivani
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;
}
};

Complexity Analysis​

  • Time Complexity: O(n)O(n), where nn is the number of integers between low and high. This is because we iterate through each number in the range.
  • Space Complexity: O(1)O(1). We use a constant amount of extra space for the counter variable.

Optimized Approach​

A more efficient approach involves using simple arithmetic to calculate the count of odd numbers. If low and high are both even, we can count how many odd numbers are in the range by the formula:

  • If both low and high are even, the number of odd numbers is (high−low2)(\frac{high - low}{2})
  • If both low and high are odd, the number of odd numbers is (high−low2+1)(\frac{high - low}{2} + 1)
  • Otherwise, the number of odd numbers is (high−low+12)(\frac{high - low + 1}{2})

Code in Different Languages​

Written by @ImmidiSivani
class Solution {
public:
int countOdds(int low, int high) {
if (low % 2 == 0) low++;
if (high % 2 == 0) high--;
if (low > high) return 0;
return (high - low) / 2 + 1;
}
};

Complexity Analysis​

  • Time Complexity: O(1)O(1), as it involves simple arithmetic operations.
  • Space Complexity: O(1)O(1), as we use a constant amount of extra space.

Authors:

Loading...