Teaching Kids Programming: Videos on Data Structures and Algorithms
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^9If the range (high – low + 1) is even, the number of even and odd numbers in this range will be the same.
If the range (high – low + 1) is odd, the solution will depend on the parity of high and low.
Count Odd Numbers in a Interval Range (Non-negative)
As the low and high are non-negative, we can use the range that gives a iterator, and then count it using inbuilt len function. We have to deal with the low being odd or even:
1 2 3 4 5 | class Solution: def countOdds(self, low: int, high: int) -> int: if low & 1: # odd number return len(range(low, high + 1, 2)) return len(range(low + 1, high + 1, 2)) |
class Solution: def countOdds(self, low: int, high: int) -> int: if low & 1: # odd number return len(range(low, high + 1, 2)) return len(range(low + 1, high + 1, 2))
Mathematically, we can count the odds between [low, high] where low is odd:
1 2 3 4 5 6 7 | class Solution: def countOdds(self, low: int, high: int) -> int: def f(a, b): return (b - a)//2+1 if low & 1: # odd number return f(low, high) return f(low + 1, high) |
class Solution: def countOdds(self, low: int, high: int) -> int: def f(a, b): return (b - a)//2+1 if low & 1: # odd number return f(low, high) return f(low + 1, high)
The number of odds between [0, low – 1] is low // 2. And the number of odds between [0, high] is (high + 1) // 2 and thus:
The number of odds between [low, high] is:
1 | (high + 1) // 2 - low // 2 |
(high + 1) // 2 - low // 2
1 2 3 | class Solution: def countOdds(self, low: int, high: int) -> int: return (high + 1) // 2 - low // 2 |
class Solution: def countOdds(self, low: int, high: int) -> int: return (high + 1) // 2 - low // 2
All algorithms are O(1) time and space – as we do not actually count.
If we want to actually count the number of odds and this will time out for sure:
1 2 3 4 5 6 7 8 9 | class Solution: def countOdds(self, low: int, high: int) -> int: if low & 1 == 0: low += 1 ans = 0 while low <= high: ans += 1 low += 2 return ans |
class Solution: def countOdds(self, low: int, high: int) -> int: if low & 1 == 0: low += 1 ans = 0 while low <= high: ans += 1 low += 2 return ans
As the time complexity is O(high – low) or O(N) where N is the number of odds in this range.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Recursive Factorial Function in BASH Programming
Next Post: Full Permutation Algorithm Implementation in BASH