PROBLEM LINK:
Setter: sayan_kashyapi
Tester: mishra_roshan
Editorialist: ritik0602
DIFFICULTY:
Cakewalk
PREREQUISITES:
Counting frequency of elements, Bitwise XOR
PROBLEM:
Given a string S made up of lower case english alphabets of length N, find if an odd occuring alphabet is present or not.
EXPLANATION
As the string consists of only lower case english alphabets, we can maintain a frequency array of size 26 and if the frequency of an element is odd print that letter and if none such exist print -1
Bitwise Solution:
As there is atmost one odd occuring element, taking the xor of all elements finally results in the odd occuring element (if any) or 0 if that is not present.
TIME COMPLEXITY
Time complexity is O(N) for traversing the string.
SOLUTIONS:
Setter's Solution
C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long int t;
cin >> t;
while (t--)
{
string str;
cin >> str;
long long int x = 0;
for (int i = 0; i < str.length(); i++)
x ^= int(str[i]);
if (!x)
{
cout << -1 << endl;
continue;
}
else
cout<<char(x)<<endl;
}
return 0;
}
Tester's Solution
Java
import java.util.*;
class Dcoder
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
String s=sc.next();
int[] h=new int[26];
for(int i=0;i<s.length();i++)
h[s.charAt(i)-97]++;
int ans=-1;
for(int i=0;i<26;i++){
if(h[i]%2!=0){
ans=i;
break;
}
}
if(ans==-1)
System.out.println("-1");
else
System.out.println((char)(ans+97));
}
}
}
Feel free to Share your approach.
Suggestions are welcomed as always had been.