Count Odd Numbers in an Interval Range — Problem & Solution
Count Odd Numbers in an Interval Range solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Count Odd Numbers in an Interval Range is an easy coding problem on math, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Math
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two non-negative integers low and high, return the count of odd numbers in the inclusive range [low, high].
Example 1
Input: low = 3, high = 7
Output: 3
Explanation: 3, 5 and 7.
Example 2
Input: low = 8, high = 10
Output: 1
Example 3
Input: low = 2, high = 2
Output: 0
Constraints
0 <= low <= high <= 1000000000
Hints for Count Odd Numbers in an Interval Range
Hint 1
Half the numbers in a long range are odd — the question is how the endpoints round.
Hint 2
(high - low) / 2counts the complete pairs.Hint 3
Add one more whenever either endpoint is itself odd.
How to solve Count Odd Numbers in an Interval Range
Half the numbers in a range are odd, rounding up when either endpoint is odd.
Approach
count = (high - low) // 2.- Add 1 if
loworhighis odd.
Why it works
The range has high - low + 1 numbers alternating in parity; the floor of half counts complete even/odd pairs, and an odd endpoint means an unpaired odd remains.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
(high + 1) // 2 - low // 2is the equivalent prefix-difference form.
Reference solution
Python
def countOdds(low: int, high: int) -> int:
count = (high - low) // 2
return count + 1 if low % 2 == 1 or high % 2 == 1 else countJava
public static int countOdds(int low, int high) {
int count = (high - low) / 2;
return (low % 2 == 1 || high % 2 == 1) ? count + 1 : count;
}C++
int countOdds(int low, int high) {
int count = (high - low) / 2;
return (low % 2 == 1 || high % 2 == 1) ? count + 1 : count;
}JavaScript
var countOdds = function(low, high) {
const count = Math.floor((high - low) / 2);
return low % 2 === 1 || high % 2 === 1 ? count + 1 : count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.