LeetCode 1523. Count Odd Numbers in an Interval Range Solution in Java, C++, Python & More | Explanation + Code

Description

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:

<li><code>0 &lt;= low &lt;= high&nbsp;&lt;= 10^9</code></li>

Solutions

Solution 1: Prefix Sum Concept

We know that the count of odd numbers in the range [0, x] is \lfloor^x+1⁄₂\rfloor. Therefore, the count of odd numbers in the range [low, high] is \lfloor^high+1⁄₂\rfloor - \lfloor^low⁄₂\rfloor.

The time complexity is O(1), and the space complexity is O(1).

PythonJavaC++GoTypeScriptRustPHPC

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

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

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

func countOdds(low int, high int) int { return ((high + 1) >> 1) - (low >> 1) }(code-box)

function countOdds(low: number, high: number): number { return ((high + 1) >> 1) - (low >> 1); }(code-box)

impl Solution { pub fn count_odds(low: i32, high: i32) -> i32 { ((high + 1) >> 1) - (low >> 1) } }(code-box)

class Solution { /** * @param Integer $low * @param Integer $high * @return Integer */ function countOdds($low, $high) { return ($high + 1 >> 1) - ($low >> 1); } }(code-box)

int countOdds(int low, int high) { return ((high + 1) >> 1) - (low >> 1); }(code-box)