Last Updated: 18 Sep, 2020
Count Even Odd
Easy
Asked in companies
You have been given an array/list of integers 'ARR' of size 'N'. Your task is to find two things-
1. The number of elements that are occurring an Odd number of times.
2. The number of elements that are occurring Even a number of times.
For Example:
ARR = [2, 1, 2, 1, 5, 5, 2]
Output: 1 2
2 occurs three(odd) times.
1 occurs two(even) times.
5 occurs two(even) times.
So, the total 1 element is occurring an odd number of times and 2 elements are occurring an even number of times.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains a single integer 'N' representing the number of elements in the array/list.
The second line of each test case contains 'N' single space-separated integers representing the array/list elements.
Constraints:
1 <= T <= 10^2
0 <= N <= 5 * 10^3
1 <= ARR[i] <= 10^9
Time Limit: 1 sec
Output Format:
For each test case, print two single space-separated integers representing the number of odd occurring elements and number of even occurring elements respectively.
The output of each test case will be printed a separate line.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Approaches
The idea is to use a hashmap to store the frequencies of all the distinct elements present in the given array/list. After that, we just traverse through these frequencies and count the number of elements with odd and even frequencies separately.
Here, is the complete algorithm-
- Declare a hashmap 'FREQUENCY'.
- Traverse through the array and add elements to the 'FREQUENCY' i.e. FREQUENCY[ARR[i]]++.
- Initialize ‘ODD_COUNT’ and 'EVEN_COUNT’ to 0.
- Now Traverse in the 'FREQUENCY' map with auto variable X:
- Here X.FIRST is the element of the array and X.SECOND is the frequency of that element.
- Increment ‘ODD_COUNT’ or ‘EVEN_COUNT’ by 1 according to the frequency of the current element i.e. X.SECOND.
- Return ‘ODD_COUNT’ and ‘EVEN_COUNT’ in a vector.