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

The answer is (D).

#include <stdio.h>

int main(void) {

return 0;
}

int anagram (char *a, char *b) {
/*
ASCII characters are of 7-bits 
so we use count array to represent all the ASCII characters 
(ranging 0-127)
*/
int count [128], j;

/*
so this loop will initialize count of all the ASCII characters to be 
0 (zero)
*/
for (j = 0;  j < 128; j++) count[j] = 0;	

j = 0;
/*
"a[j] && b[j]"  ensures that anagram returns 0 (false) in case both 
strings have different length. Because different length strings cannot
be anagram of each other
*/

/*
Logic:

Below while loop increments ASCII equivalent position for its occurence
in array 'a'in count array; and decrements ASCII equivalent position 
for its occurence in array 'b'in count array.

Example: a = "ISS" and b = "SIS"
ASCII equivalent of:
I - 73
S - 83

j = 0:	Statement A will increment count[ASCII of 'I']==>count[73] 
count[73] = 0 --> 1
Statement B will decrement count[ASCII of 'S'] ==> count[83]	
count[83] = 0 --> -1 and will increment j	j = 0 --> 1

j = 1:	Statement A will increment count[ASCII of 'S'] ==> count[83]	
count[83] = -1 --> 0 
Statement B will decrement count[ASCII of 'I'] ==> count[73]	
count[73] = 1 --> 0 and will increment j	j = 1 --> 2

j = 2:  Statement A will increment count[ASCII of 'S'] ==> count[83]	
count[83] = 0 --> 1 
Statement B will decrement count[ASCII of 'S'] ==> count[83]	
count[83] = 1 --> 0 and will increment j	j = 2 --> 3

*** END OF LOOP ***	

*/
while (a[j] && b[j]) {


A;	//count [a[j]]++

/*
Note: j will be increment after count[]-- will execute
Resource: http://www.c4learn.com/c-programming/increment-operator-inside-printf
*/
B; 	//count[b[j++]]--
}

/*
This loop checks that the number of occurences of the individual ASCII
characters is same or not.
If count[i] = 0 ---> same number of occurences for ASCII chracter i 
---> return 1 (true)

if count[i]!= 0 ---> different number of occurences for ASCII chracter i 
---> return 0 (false)
*/

for (j = 0; j < 128; j++) if (count [j]) return 0;
return 1;
}

Comments

You are right bro @Nitesh Singh 2 string length should be match otherwise we might get wrong result like:

---

More visualization

https://youtu.be/y6ht-CoRI4Q?si=BcU3ukfONEuZ6zTq

---

Nice Answer

Answer 2

Answer is (D)

A:  Increments the Count by 1 at each index that is equal to the ASCII value of the alphabet it is pointing at

B: Decrements the count by 1 at each index that is equal to the ASCII value of the alphabet it is pointing at . Also it increments the loop counter for next iteration.

If one string is permutation of other ,there would have been equal increments and decrements at each index of array and So count should contain zero at each index.that is what the loop checks at last and if any non-zero elements is found, it returns 0 indicating that strings are not anagram to each other.

Comments

@Arjun 

thank you sir , It was really overwhelming to learn concept of "Sequence point in C" .

I have gone through many other links apart from one provided by you

https://stackoverflow.com/questions/3575350/sequence-points-in-c

https://www.geeksforgeeks.org/sequence-points-in-c-set-1/

https://en.wikipedia.org/wiki/Sequence_point

https://www.quora.com/What-are-sequence-points-in-C-C++

I think you yourself canceled my answer to http://gateoverflow.in/3702/gate2004-it-59

thanks for clarifying that question.

I wonder how many  more concept will be there in C like this one which even after studying / coding / solving mcq's for approximately six year I still don't know.

It would be silly to ask , but do you know any more concept like this which even people with moderate experience probably don't know?

---

If you're solving MCQs there might be many more because such is the standard of most MCQ books :)

---

concise answer

Answer 3

I would like to answer this

An anagram of string mean you are just channging the arrangements of alphabets in string 1 to get a another string S2.

where no of occurrences of a  character in string S1 should be equal to no of occurrences of a character in string s2

. Supose if s1= abc

then s2=cba

Now if  i see code . an array of size 128 is nothing but a total of ASCII charcaters .we have initalized to zeros

now the main logic lies here is for every character that come first in any of string  say A we will go to ascii postion ie 65 and we will increment (while we are traversing ) and when this A come later in other string s2 then we will decrement. so carrying this for both the string we should get all elements of A[128] back to zero again . if we get any non zero value then it violate occurrence as stated above

Option a) and b are wrong because you are just checking first character of string there is no increment thing .So we cant say string are anagram by just checking charcter

option c ) is wrong too

beacuse in count [a[j++]|++ if currently i =o and then after exceuting i =1

and when it goes to B statament it check from 1 index of string and not from 0 index . we are leaving a charcter in each iteration

Option d ) Work perfectly fine . You first check character of string at index i , after doing that B increment so while loop can be excutued for other part of strings

NOTE : while (a[j] && b[j]]) is one that can be used to check anagarm string should be always of same length . If one is shorter or bigger the loop breaks and then they are not anagarm of each other :)

Comments

i am confused about how the while loop breaks if a=''DBC" and b="BD" .

i suppose here both occurence of B and D will have zero count in count arrray when for loop is checked. please explain?

---

explanation is nice just edit your answer by changing "i" by "j"...

beacuse in count [a[j++]|++ if currently j =o and then after exceuting j =1

and when it goes to B statament it check from 1 index of string and not from 0 index . we are leaving a charcter in each iteration

Option d ) Work perfectly fine . You first check character of string at index j , after doing that B increment so while loop can be excutued for other part of strings

---

@Dexter Thanks !....finally understood the code .

Answer 4

If you don't want to read all those long answers. Here the smaller way, the way I analyzed it.

1. Anagram, as given in question "abc", is an anagram of "cba".

2. Always try to run a complicated code with a very small example like above, you'll find out that if two string are permutations of each other than they make count[ ] array all 0 in last.

3. we can also state the point 2 as the last line of the program want for( .... ) if(count [j]) return 0, i.e. if at any position other than 0  is found return with a message "Hey ! this is not an anagram."

 

options given:-

• option c) A : count [a[j++]]++ and B : count[b[j]]--
• option d) A : count [a[j]]++and B : count[b[j++]]--

 

1. Then when you try to fill A & B, we are given j=0 intially but how to increment the j? you'll notice that j need to increased somehow this will eliminate option a) & b) as there is no 'j++' in them and we need to increase j to read full array A[ ] B[  ]. 

2. the only option left is c) and d) now, as is option c) if j get increased in A(first line we need to fill) then we will mismatch the positions like as ( j=0 given before loop,see above in option c) A=count[0] and as post-increment happen B=count[1], but we need to increase j such that a[j] & b[j] have same value so only option d) remain which has 'j++' at correct position, because of which j will increase for next iteration of loop.

Comments

@bhuv @Arjun Sir everything is clear but still  i am not getting how the condition inside while loop is comparing the lengths as according to me a[i] && b[j]  compares the two corresponding letters in a and b string

---

@dharmesh7

how the condition inside while loop is comparing the lengths as according to me a[i] && b[j]  compares the two corresponding letters in a and b string

NO the condition in while loop is not comparing the two letters in a and b string. if it was the case then we do not need to put the statements A and B.  Here the while loop is just to keep a track on the length of both the string as they must be of equal length and suppose string b is smaller than a  then at that time for that particular j index . b will give 0 and thus the while loop condition will fail .

Answer 5

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 6

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