Count Even Odd

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
4 upvotes
Asked in companies
BarclaysCapegemini Consulting India Private LimitedTeradata

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”.
Detailed explanation ( Input/output format, Notes, Images )

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
Sample input 1 :
3
abbadef
bbbb
xyz
Sample output 1 :
EVEN
ODD
ODD
Explanation for sample output 1 :
(i) For the first string M=2 which is even.
(ii) For the second string M=1 which is odd.
(iii) For the third string M=1 which is odd.
Sample input 2 :
3
abbc
bbdddd
z
Sample output 2 :
ODD
EVEN
EVEN
Explanation for sample output 2 :
(i) For the first string M=3 which is odd.
(ii) For the second string M=2 which is even.
(iii) For the third string M=0 which is even.
Hint

Think about iterating over the whole string and find the frequency of each character.

Approaches (3)
Brute Force

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.

  1. Let’s say we have given a string STR.
  2. 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.
  3. Return “EVEN” if M is even, otherwise return “ODD”.
Time Complexity

O(N), where ‘N’ is the length of the string.

 

As for each character we are iterating over the whole string 26 times so time complexity is  O(N*26).

Space Complexity

O(1).

 

As we are not using any extra memory.

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