Count Even Odd

Easy
0/40
Average time to solve is 10m
24 upvotes
Asked in companies
WalmartAdobeTech Mahindra

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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. 
Sample Input 1:
2
5
4 5 1 2 1
4
2 1 2 1 
Sample Output 1:
3 1
0 2
Explanation for Sample 1:
In the first test case, three integers(4, 5 and 2) occur odd times and the only integer 1 occurs even times.

In the second test case, no integer occurs odd times and two integers(1 and 2) occurs even times.
Sample Input 2:
1
8
5 2 9 9 7 5 1 3
Sample Output 2:
4 2
Hint

Store frequencies with the help of some Data Structures.

Approaches (1)
Hashmap Solution

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

O(N),  Where ‘N’ is the number of elements in the array/list.

 

We will traverse the array and the hashmap exactly one time and the hashmap operations take constant time.

Space Complexity

O(N), Where ‘N’ is the number of elements in the array/list.

 

When all the elements in the array/list are different, we will have ‘N’ key-value pairs in the hashmap.

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