Given two positive integers. Count the number of pairs (a, b) such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even.
Examples:
Input: 2 7 Output: Count of pairs is 7 Input: 1 1 Output: Count of pairs is 1 Input: 4 9 Output: Count of pairs is 18 Input: 3 5 Output: Count of pairs is 8
Simple Approach :
A simple approach will be to run two nested loops to count all possible pair of elements such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even.
If yes then we increment count and return the count.
Implementation:
// A O(n ^ 2) time and O(1) extra space C++ program to
// count the number of pairs (a, b)
// such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even
#include <bits/stdc++.h>
using namespace std;
// Returns the number of pairs (a, b)
// such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even
int getPairsCount(int x, int y) {
int count = 0;
for (int i = 1; i <= x; i++) {
for (int j = 1; j <= y; j++) {
if ((i + j) % 2 == 0) // check pair is even or not
count++;
}
}
return count;
}
// Driver function to test the above function
int main() {
int x = 2, y = 7;
cout << "Count of pairs is " << getPairsCount(x, y);
return 0;
}
Output:
Count of pairs is 7
Time Complexity: O(n^2)
Auxiliary Space: O(1)
Efficient Approach :
If a is even and b is even then sum of pair (a,b) is also even but if a is odd and b is odd then sum of pair (a,b) will be even.
Total even numbers between 1 to x will be x/2
Total odd numbers between 1 to x will be (x+1)/2
Total even numbers between 1 to y will be y/2
Total odd numbers between 1 to y will be (y+1)/2
Therefore, the number of pairs (a,b) where a+b is even :
(x/2) * (y/2)+((x+1)/2)*((y+1)/2)
Implementation:
// A O(1) time and O(1) extra space C++ program to
// count the number of pairs (a, b)
// such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even
#include <bits/stdc++.h>
using namespace std;
// Returns the number of pairs (a, b)
// such that 1 ≤ a ≤ x, 1 ≤ b ≤ y and a+b is even
int getPairsCount(int x, int y) {
int even_x = x / 2; // store the half of x
int even_y = y / 2; // store the half of y
int odd_x = (x + 1) / 2;
int odd_y = (y + 1) / 2;
int res = even_x * even_y + odd_x * odd_y;
return res;
}
// Driver function to test the above function
int main() {
int x = 2, y = 7;
cout << "Count of pairs is " << getPairsCount(x, y);
return 0;
}
Output:
Count of pairs is 7
Time Complexity: O(1)
Auxiliary Space: O(1)