Last Updated: 4 Jan, 2021

Count Even Odd

Moderate

Asked in companies

Capegemini Consulting India Private Limited

Solve now

Problem statement

You are given a string of lowercase characters. A magic number M is the summation of the count of characters that occupy even positions in English alphabets and have even frequency, and the count of characters that occupy odd positions in English alphabets and have an odd frequency.

You have to return “EVEN” if M is even, otherwise return “ODD”.

For example:

If we are given a string ‘aabb’.Then we can see the frequency of a=2 and b=2. The position of ‘a’ in alphabets is 1 and the position of ‘b’ is 2. So ‘a’ has an even frequency but its position is odd, so it will not contribute to M. As ‘b’ has an even frequency and its position is also even, so M=1. Now M =1 which is odd, so we have to return “ODD”.

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases. The 'T' test cases follow.

The first and only line of each test case contains a string 'STR'.

Output format :

For each test case, print “EVEN” if M is even, else return “ODD” without quotes.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 10 ^ 4

Time limit: 1 sec

Solve now

Approaches

01 Approach

We will find the frequency of all characters by iterating over the whole string 26 times. On completion of iteration if the frequency of character is odd and the position of the character is odd, increase M by 1, otherwise if the frequency of character is even and the position of the character is even, increase M by 1.

Let’s say we have given a string STR.
Iterate over STR[i] for each 0 <= i < 26 and do:
1. Initialize an integer variable COUNT=0
2. Initialize an integer variable M=0.
3. Initialize an integer variable POS=i+1.
4. Initialize a char variable ALPHA= (’a’+i).
5. Iterate over STR[j] for each 0 <= j < N and do:
  1. ALPHA = STR[j] then increase COUNT by 1.
6. If COUNT is even and POS is even, increase M by 1.
7. If COUNT is odd and POS is odd, increase M by 1.
Return “EVEN” if M is even, otherwise return “ODD”.

Solve now

02 Approach

We will scan the string from left to right and we will use the Hash to store the frequency of each character.

Let's say we have given a string STR.
We are using an integer array of size 26 initialized to zero, say HASH[26]={0}.
Iterate over STR[i] for each 0 <= i < N and do:
1. HASH[STR[i]-’a’] += 1
Initialize an integer variable M=0.
Iterate over HASH[i] for each 0 <= j < 26 and do:
1. COUNT = HASH[i]
2. POS = i+1
3. If COUNT is even and POS is even, increase M by 1.
4. If COUNT is odd and POS is odd, increase M by 1.
Return “EVEN” if M is even, otherwise return “ODD”.

Solve now

03 Approach

We generally have INT of 4 bytes or we can say 32 bits. So we are going to use the bits of INT to store the frequency of characters. We are going to use two integers for the purpose say EVEN and ODD.

As for odd positions we just need to check if the frequency is odd or not, the corresponding bit will be 0 initially and we will XOR the bit on encountering the character. And in last if the bit is 1 we can say we have an odd frequency.

As for even positions we just need to check if the frequency is even or not, the corresponding bit will be 0 initially and we will XOR the bit on encountering the character. And in last if the bit is 0 we can say we have an even frequency, with one exception when the frequency is 0, also then the final bit will be zero. So we need to make sure that at least frequency is greater than 1.

Let's say we have given a string STR.
Initialize two integer variables EVEN=0 and ODD=0.
Iterate over STR[i] for each 0 <= i < N and do:
1. POS = STR[i]-’a’+1
2. If POS is odd then do:
  1. ODD = ODD ^ (1<<POS), (flipping the bit).
3. If POS is even then do :
  1. EVEN = EVEN ^ (1<<POS) , (flipping the bit).
  2. ODD = ODD | (1<<POS) , (to make sure frequency is greater than 0).
Initialize an integer variable M=0.
Iterate 1<= j <= 26 and do:
1. If j is odd then do:
  1. If ODD & (1<<POS) = 1,then M=M+1.
2. If j is even then do :
  1. If EVEN & (1<<POS) = 0 (Checking if frequency is even)
  2. If ODD & (1<<POS) = 1 (Checking if frequency is greater than 0)
  3. If both the above conditions satisfied then M=M+1.
  4. Return “EVEN” if M is even, otherwise return “ODD”.

Solve now