GATE IT 2005 | Question: 53

Question

The following$ C$ function takes two ASCII strings and determines whether one is an anagram of the other. An anagram of a string s is a string obtained by permuting the letters in s.

int anagram (char *a, char *b) {
    int count [128], j;
    for (j = 0;  j < 128; j++) count[j] = 0;
    j = 0;
    while (a[j] && b[j]) {
        A;
        B;
    }
    for (j = 0; j < 128; j++) if (count [j]) return 0;
    return 1;
}

Choose the correct alternative for statements $A$ and $B$.

• A. A: count [a[j]]++ and B: count[b[j]]--
• B. A: count [a[j]]++ and B: count[b[j]]++
• C. A: count [a[j++]]++ and B: count[b[j]]--
• D. A: count [a[j]]++ and B: count[b[j++]]--

Comments

I think there is something wrong in the return statement because if we run then it will just check 1st index of the count and return either '0' or '1'.So other value of count is not checked.

@Vicky rix please explain this to me.

---

@soumayan bandhu

No. return 1; is not part of if (also, not part of for loop as well). Hence, the for loop is going to check the value for each corresponding ASCII value, if it not equal to 0, then it will execute return 0;

---

In the expression count[b[j++]]−−  two post operations are present and precedence of ‘[ ]’ is highest so post increment( j++) should be evaluated before post decrement( count[b[j]]−− ) but for the code to work properly decrement should happen before increment. So can anyone tell me what is the order of evaluation in these kind of expressions where more than one post operations are present?

Answer 1

Let's analyse this code.

int anagram (char *a, char *b) {                       //Line 1
    int count [128], j;                                //Line 2
    for (j = 0;  j < 128; j++) count[j] = 0;           //Line 3
    j = 0;                                             //Line 4
    while (a[j] && b[j]) {                             //Line 5
        A;                                             //Line 6
        B;                                             //Line 7
    }                                                  //Line 8
    for (j = 0; j < 128; j++) if (count [j]) return 0; //Line 9
    return 1;                                          //Line 10
}                                                      //Line 11

• Line 2 creates an array named count which contains 128 elements, and then Line 3 assigns the value 0 to all of them.
   
• Line 5 says "until both strings have a char"
   
• By Line 9 and 10, we can figure out that if at the end, any element of count array is $\neq 0$, 0 is returned => False. => Strings aren't anagrams.
  So, True/1 is returned only when all the elements of count array are 0 at the end.
   
• Now, one of the possible substitues of $A$ is $count[a[j]]++$
  How to figure out what this is?
  j = 0 as told by line 4, so put that.
  $count[a[0]]++$
  Now a[0] would be the first letter of the first input string. Assume that is d.
  So, $count[d]++$
  count[d] would take you to the index in count array, which is equal to the ASCII value of d.
  
  So, we deduce that in count array, the indices are nothing but the ASCII values of all the letters of the alphabet, and other irrelevant ASCII literals (The hint given to us was "128". ASCII values are of 7 bits, so total values possible are $2^7=128$)
  
  So $count[d]++$ would increment the value at "ASCII index" of d.
  
  This was a sample. We require a mechanism to increment count for first input string, and then decrement count for second input string, so that when both strings are parsed, the final value of each element of count array is 0 for anagrams.
  
  Also, we need a mechanism to increment j itself. That's how it'll go forward to other letters of the input strings.
  
  Keeping that in mind, it's either Option C or D because Options A and B don't increment j.
  
  Out of C and D, C would increment j too soon. We want to increment j after both counts are registered for a given j, so j must be incremented at the end. Hence, Option D is the correct choice.

Comments

Thankyou so much @jashanArora. Your answer cleared all my doubts.

Answer 2

The best answer here is very much in detail

Answer-D

Smart step for this question is to look this

This clearly says that if count !=0, then we have to return false,

This means, if two strings have matched successfully, our count should be zero so that we will get count[j]=0 at the end of our computation

 

Now look each option one by one, you will find that

Option D is the only candidate for this kind of operation.

What we are doing is

We are adding the ascii values of each character in string A, and subtracting the ascii value of each character in string B.

In this code, we are moving one step by step, and incrementing the j smartly in the second count[b[j++]]—

 

So clearly you have to visualize these kind of questions

 

Thanks