CareerCup

With no additional storage, you can sort and compare O(nlgn)
With additional storage, its O(n)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

unsigned int charsum(char *str)
{
  unsigned int x = 0;
  unsigned int i;
  for(i = 0; i < strlen(str); i++)
    x += str[i];
  return x;
}

int anagram(char *str1, char *str2)
{
  return charsum(str1) == charsum(str2);
}

int main(int argc, char**argv)
{
  if (argc != 3)
  {
    printf("usage: %s str1 str2\n");
    exit(1);
  }
  int x = anagram(argv[1], argv[2]);
  printf("%s and %s are%s anagrams.\n", argv[1], argv[2], x ? "" : " NOT");
}

$ ./anagram abcdefg bdagfce
abcdefg and bdagfce are anagrams.

$ ./anagram foo bar
foo and bar are NOT anagrams.

int findAna(char *s1, char*s2){

int sum = 0;

while(*s1 != '\0')
sum ^= *s1++;
while(*s2 != '\0')
sum ^= *s2++;

return sum;

}

void main (){

int i;

i = findAna("abcd","bac");

printf("%d",i); // i = 0 ? => anagrams .... else not anagrams :)
}

First compare the lengths of the two strings s1 and s2. If they are unequal, return false. If they are equal, then put s2 in a Hash Map. Iterate through s1 character by character. In each iteration, query the character of s1 with the Hash Map. If a collision occurs, increment a "collision counter" variable that keeps track of the total number of collisions at the end of the iterations. At the end, compare the length of the string with the value of the counter. If they are equal, that means there have been as many collisions as there are characters in the two strings, which consequently implies that the two strings s1 and s2 are anagrams of each other.

It can be done in O(n) runtime and O(1) space. See question id 8248783.

Why cant we just Xor all the characters in both the arrays and check if the result is 0