CareerCup

If external storage(like a hash table with the value as the index) is allowed, then we only need to traverse the string once, whenver one value is seen, just increment the counter associated with that value in the table.
After the traversal, look at the table and output if odd occurrences are seen.

You can do it in one pass with constant space. No extra space if you can destroy the array.

int total=0;
for(int i=0;i<strlen(str);++i)
{
  total=str[i]-total;
}
return total;

This is possible in one pass without external storage and has a complexity of O(n)

char find_odd_character(char* str)
{
  int i=1, cnt=1;
  char c;
  c=str[0];
  while(str[i]!='\0')
  {
    if(c!=str[i])
    {
       if(cnt%2!=0)
         break;
       else
       {
         c=str[i];
         cnt=1;
       }
    }  
    i++;
  }
  return c;
}

Sorry! missed some lines

char find_odd_character(char* str)
{
int i=1, cnt=1;
char c;
c=str[0];
while(str[i]!='\0')
{
if(c!=str[i])
{
if(cnt%2!=0)
break;
else
{
c=str[i];
cnt=1;
}
}
else
cnt++;
i++;
}
return c;
}

Just realized that the example above in a little misleading. My code assumed that the characters are sorted. In this case to get a complexity of O(n) we would need some extra storage.

Create an array of size 256 with all elements initialized to 0. Scan the string(str) and increment the appropriate position(str[i]-'a') in the array for each character. Then scan the array and the entry with an odd number is the character that occurs odd number of times.

char oddchar(char ch[])
{
char x = 0;
int i = 0;
while(ch[i])
{
x = x ^ ch[i];
i++;
}
return x;
}

@Ravi

Ur code doesnt run in all the cases. What if there are two characters occuring odd # of times in src string. It doesnt run.

If its a char array, just do a XOR...

char t;
t = a[0];
for(int i=1; i < n; ++i)
  t = t ^ a[i];