Leetcode 1523. Count Odd Numbers in an Interval Range
Problem Explanation
Given two non-negative integers low
and high
, the task is to count the number of odd integers between low
and high
inclusive.
For instance, if low = 3
and high = 7
the odd numbers between 3 and 7 are [3,5,7], so the output should be 3
.
The simplest way to approach this problem is to iterate from low
to high
and count the total number of odd numbers. But this can be simplified to a mathematical formula to optimize performance.
Solution Explanation
The mathematical solution involves dividing each limit (low
and high
) by 2
. The integer division of the high
limit (plus 1
to include this limit in the count if it is odd) represents the count of odd numbers up to high
, and the integer division of the low
limit represents the count of odd numbers before low
. The difference between these two results is the count of odd numbers between low
and high
inclusive.
Python Solution
1 2python 3class Solution: 4 def countOdds(self, low: int, high: int) -> int: 5 return (high + 1) // 2 - low // 2
In the Python solution, we use the integer division operator //
to carry out the formula.
Java Solution
1
2java
3class Solution {
4 public int countOdds(int low, int high) {
5 return (high + 1) / 2 - low / 2;
6 }
7}
In Java, we use the /
operator to carry out integer division.
JavaScript Solution
1
2javascript
3class Solution {
4 countOdds(low, high) {
5 return Math.floor((high + 1) / 2) - Math.floor(low / 2);
6 }
7}
In JavaScript, we have to use Math.floor()
function with the division operator /
to carry out integer division.
C++ Solution
1
2cpp
3class Solution {
4public:
5 int countOdds(int low, int high) {
6 return (high + 1) / 2 - low / 2;
7 }
8};
In C++, we use the /
operator to carry out integer division.
C# Solution
1
2csharp
3public class Solution {
4 public int CountOdds(int low, int high) {
5 return (high + 1) / 2 - low / 2;
6 }
7}
In C#, we also use the /
operator to carry out integer division.# Conclusion
At first glance, the problem of counting the odd numbers between two given non-negative numbers might seem like a simple task of iterating through the numbers and counting. However, as demonstrated above, this can be simplified to a mathematical solution that is more efficient and optimal. The solutions provided in Python, Java, JavaScript, C++, and C# show how the theory can be implemented in different programming languages.
Regardless of the language though, the basic principle remains the same - calculating the number of odd integers by dividing each limit (low and high) by 2, then subtracting the two results. This logic can be applied to a range of other similar problems and demonstrates a smart way of thinking about and approaching problems in computer programming.
These type of problems not only test programming knowledge and language syntax, but more importantly, they test your ability to problem solve and think logically, applying mathematical concepts, where appropriate, to create the most efficient solutions. This increases the overall performance of the application where this is implemented. Therefore, understanding such solutions and their underlying concepts helps you in enhancing your analytical thinking and coding abilities.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.