GATE CSE 2003 | Question: 90

Question

Consider the function $f$ defined below.

struct item {
        int data;
        struct item * next;
};
int f(struct item *p) {
    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));
}

For a given linked list $p$, the function $f$ returns $1$ if and only if

• A. the list is empty or has exactly one element

• B. the elements in the list are sorted in non-decreasing order of data value

• C. the elements in the list are sorted in non-increasing order of data value

• D. not all elements in the list have the same data value

Comments

I still dont understand why is a not correct it is an or condition if (p==NULL||(p->next==NULL)||((p->data<=p->next->data)&&f(p->next))) all 4 coditions are in or even if one is true  it can return 1 plz explain

---

$A$ if and only if $B$ means both $A\rightarrow B$ as well as $B\rightarrow A$ hold.

So is the function returning 1 only when the list is empty or has exactly one element? NO

because it also returns 1 for  ((p->data <= p ->next -> data) && f(p->next)) which is nothing but C ! So C is the most appropriate choice.

---

C means it sat that its a decreasing order list....is it possible??

---

Some one please give better answer

---

Suppose You Choose Option A

Then According to Question

For a given Linked list p, the function f returns 1 if and only if the list is empty or has exactly one element. 

​​​Which is false because, a non empty list or a list containing more than one element will also return 1. 

Option B is correct because,

For a given Linked list p, the function f returns 1 if and only if the elements in the list are sorted in non-decreasing order of data value. 

Non Decreasing Order of data value can be 

1,2,3,4,5 or

4,5,5,6,7 etc. 

 

 

 

---

If someone has confusion how function return terminating value

return(0 || 1 || (......) );

the ..... part will not execute as here || operator used and when it gets 1 it will not check or execute right part.

---

If and only if means ==> necessary and sufficient condition. 

But the list is empty or has exactly one element is not necessary and sufficient condition to return 1 for the function f.

Because a non empty list, a list containing more than one element (which is non-decreasing order in data value) will also return 1. 

So option A is not true. 

---

Thanks a lot

---

Actually the Option $A$ is also true it is just that Option $B$ is a more stronger option in the sense option $A$ is also covered under it.

---

@GyanuVery clear and good example and explantation 
But if someone thinks that option A counters option B  under the condition in question "If and only if " then 

---

@ninjahatori1

---

I guess an element containing only NULL or only one element can be considered increasing and decreasing and not increasing nor decreasing because there is no other element to compare to contradict the type of list. So option B also encompasses the option A in itself. Suppose if the answer is option C then it also encompassed option A also.

Correct me if I am wrong.

---

the condition is true only if one of the below condition holds 

1. list is emtpy

2. list has only 1 node 

3. for an element at node index i, element at node index i+1 is greater than equal to node value at i , for all i , 

this means that, we need the next index value either increasing or similar to current index which is a condition for a non-decreasing array where values remains constant or increases but never decrease throughout the array.

hence, this list elements are sorted in non-decreasing order which is mentioned by option C.

---

another question dictating the power of if and only if. Many would say answer A is correct but it's not, the question says function return if and only if means if option A is correct then every other option will return 0, but is that the case? No.

But if and only option B is there then yes for an empty list and for element with 1 element option B is true.

---

Bcz of Iff condition option A is wrong here.

List empty or one element -> return 1
But , returns 1 -> List empty ( this fails).

1 ->2->2->3->4->NULL

this also returns 1 ,

so returns 1 doesnt only meant list empty or having one element

Answer 1

It returns $1$ if and only if the linked list is sorted in non-decreasing order- (B) option.

It returns $1$ if the list is empty or has just $1$ element also, but if and only if makes (A) option false.

Comments

@ ankitrazzagmail.com

If and only if makes option A incorrect, but it also makes option B incorrect.

 

NO i can’t make B incorrect because A is included in B.

    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));

here due to f(p→ next ) it do recursive call again and again and finally reaches the value where               p->next == NULL.

Hope this helps!

I think actual answer is : the list is empty OR has exactly one element OR the elements in the list are sorted in non-decreasing order of data value.
 

And yes this is also the answer if it is given in the options but it is not isn’t it... 

---

@Ruchi Vora
Plz refer Link

---

Quote of the day : Neglegence reading can cost you -0.33

Answer 2

How to approach this:-

Emphasize on Word "if and only if"

Read all options carefully ..eliminate the wrong ones.

A. May Correct but due to if and only if Check remaining options.

C. False . Example:->5,5,4 it wont return 1.(still optionA may correct).

D. False. Example:->> 8,2,10 it wont return 1(still option A may correct).

B.Example:->>  1,1,2  it returns 1

So here Option A becomes wrong Now So option  B is correct.

(Check another large list also 1,2,2,3,3 still returns1 So finally Option B is Ans.)

Comments

The cause "if and only if" makes both option (a) and (b) wrong. How to handle this ?

---

@arjun sir

please expalin 4 the option through example .I m not getting this

Answer 3

Here is the idea :

Answer 4

#include <stdio.h>
#include <stdlib.h>
struct item {
    int data;
    struct item * next;
};
void print(struct item *lhead)
{
    while(lhead!=NULL)
    {
        printf("%d ",lhead->data);
        lhead = lhead->next;
    }
}
int f(struct item *p) {
    return ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));
}
int main(void) {
    // your code goes here
    int t,i=0;
    //printf("Number of testcases:");
    scanf("%d",&t);
    while(t--)
    {
        struct item *head = NULL;
        int n;//number of nodes
        //Number of nodes 
        scanf("%d",&n);
        int d;//data;
        struct item *temp;
        while(n--)
        {
            scanf("%d",&d);
            temp = malloc(sizeof(struct item));
            temp->data = d;
            temp->next = head;
            head = temp;
        }
        
        printf("\nThe elements are for case %d:\n",++i);
        print(head);
        printf("\nReturn value for case %d:",i);
        printf("%d",f(head));
    }
    printf("\n");
    return 0;
}

Output is:

    

From above we can clearly see A is not sufficient, we can get 1 when we have elements in non-decreasing order

whereas in option B we get return value 1, as well as option A, is also contained in Option B

Hence B is a more appropriate answer than A

Answer 5

This question is only observation based.

the condition given is 

 ((p == NULL) || (p->next == NULL)|| 
        ((p->data <= p ->next -> data) &&
        f(p->next)));

here in the second line of code we are given that p-> data <= p-> next ->data . It means that the data stored in the address of p pointer  must be smaller or equal to the data in the next node i.e p->next->data. Eg- 2->2-.3->4 which is in non decreasing order and also more valid than option A. So,this condition is only satisfied by option B.

Comments

Also non-decreasing order allows null or single node are also valid

Answer 6

Here if and only if word is important . Option A will be wrong because even if the linked list is not empty the function will still return 1 . So the whole idea of  S: A$\Leftrightarrow$B  fails as  S can still be made true even after B is false .