Last Updated: 16 Apr, 2021
Count The Odd Numbers
Easy
Asked in company
Given two integers ‘LOW’ and ‘HIGH’, your task is to find the total number of odd integers between the interval [LOW, HIGH]. Here both ‘LOW’ and ‘HIGH’ are inclusive.
Input format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains two space-separated integers, ‘LOW’ and ‘HIGH’, denoting the start and end of the interval respectively.
Output format:
For each test case, print a single line containing a single integer denoting the total count of odd numbers present between ‘Low’ and ‘High’ both inclusively.
The output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 1000
0 <= LOW<= 10 ^ 9
LOW <= HIGH <= 10 ^ 9
Where ‘T’ represents the number of test cases, ‘LOW’ represents the start of the interval and ‘HIGH’ represents the end of the interval.
Time Limit: 1 sec.
Approaches
Approach:
- It is a brute force approach where we will traverse through the interval Low to High and count the odd numbers present between them.
- To check whether a particular number is odd, we will find its remainder by dividing it by 2. If the remainder is 1, then the number is odd.
Algorithm:
- Create a variable count initialized to 0 to maintain the count of odd numbers.
- Traverse from Low to High and for each number check the following condition:
- If on division of the number with 2 it does not leave a remainder 0, then the number is an odd number.
- If the current number is an odd number, then we will increment count by 1.
- Finally, return the count as the answer.
Approach:
- The idea of this approach is to find the count of odd numbers from 1 to N.
- The series will look like 1, 3, 5, …… N. We can observe that all the numbers from 1 to N form an arithmetic progression with a common difference of 2. So we can count the total number of odd integers using the formula
(Nth term Of AP) = First Term Of AP + (Count - 1)*(Common Difference) - This gives us the total number of odd numbers (Count) from 1 to N, i.e., (N + 1) / 2.
- Now if we find total odd numbers from (1 to High) and total numbers from (1 to Low - 1) then it will give us the total number of odd numbers between (Low to High).
- Therefore,
OddNumbers(Low, High) = OddNumbers(1, High) - OddNumbers(1, Low-1) which is equal to (High + 1)/2 - Low / 2.
Algorithm:
- Create a variable ans which is equal to (High + 1) / 2 - Low / 2.
- And return ans as our required answer.