Count The Odd Numbers

Easy
0/40
Average time to solve is 15m
0 upvote
Asked in company
Flipkart limited

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
1 6
5 10
Sample Output 1:
3
3
Explanation 1:
For the first test case, 
All integers between LOW = 1 and HIGH = 6 are [1, 2, 3, 4, 5, 6] and the odd numbers present between them are [1, 3, 5]. So the output will be 3.

For the second test case, 
All integers between LOW = 5 and HIGH = 10 are [5, 6, 7, 8, 9, 10] and the odd numbers present between them are [5, 7, 9]. So the output will be 3.
Sample Input 2:
2
3 7
8 10
Sample Output 2:
3
1
Hint

Odd numbers are those for which when divided by 2 does not leave a remainder 0.

Approaches (2)
Brute Force

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.
Time Complexity

O(N), where ‘N’ is equal to (High - Low + 1).

 

Since the length of the interval will be N = High - Low + 1 and traversing over N elements will take O(N) time. So the overall time complexity will be O(N). 

Space Complexity

O(1).

 

Since constant space is being used. So overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Count The Odd Numbers
Full screen
Console