The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Check if two strings are anagrams.
A word 'x' is an anagram of word 'y', if 'y' can be formed by rearranging the letters of the word 'x'.
For e.g, cat & act are anagrams.

Solution :-
We know that zor of two identical characters is '0'.
1 zor 1 = 0
a zor a = 0
So, if we zor all the characters of the two strings and we get 0, then the two strings are anagrams.
Though the zor condition is necessary for the two strings to be anagrams, it is not sufficient because the algorithm will fail for some cases. For e.g, if the input strings are aaa and bbb, then zor of all the characters will be 0 but we can see that the two strings are not anagrams. So, we need to put another check. We will compute the sum of ascii values of the two strings ( sum1 for 1st strings and sum2 for second string) and then check if sum1 is equal to sum2. See the program below.

#include<iostream>
using namespace std;

// check if two strings are anagrams
bool isAnagram(char str1[], char str2[], int size) {
   // zor of equal values is zero
   int zor = 0, i;
   int sum1 = 0, sum2 = 0;
   for(i = 0; i < size; i++) {
      zor ^= str1[i];
      zor ^= str2[i];
      sum1 += str1[i];
      sum2 += str2[i];
   }
   if(zor == 0 && sum1 == sum2)
      return true;
   return false;
}

// main
int main() {
   char str1[] = "this is a string";
   char str2[] = "gtha si  istsrin";
   int size = sizeof(str1)/sizeof(char);
   bool is_anagram = isAnagram(str1,str2,size);
   if (is_anagram)
      cout<<"\nInput strings are anagrams";
   else
      cout<<"\nInput strings are not anagrams";
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)