Please explain...

16 votes

Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.

Node *remove-duplicates (Node* head, int *j) { Node *t1, *t2; *j=0; t1 = head; if (t1! = NULL) t2 = t1 ->next; else return head; *j = 1; if(t2 == NULL) return head; while (t2 != NULL) { if (t1.val != t2.val) ----------------> (S1) { (*j)++; t1 -> next = t2; t1 = t2; -----> (S2) } t2 = t2 ->next; } t1 -> next = NULL; return head; }

Assume the list contains $n$ elements ($n\geq 2$) in the following questions.

- How many times is the comparison in statement $S1$ made?
- What is the minimum and the maximum number of times statements marked $S2$ get executed?
- What is the significance of the value in the integer pointed to by $j$ when the function completes?

24 votes

Best answer

7 votes

*Ans : n-1*)

2. S2 executes when values at t1 & t2 are unequal.

Case Max : no duplicate element in list. (*Ans : n-1*)

Case Min : All nodes have same value. (Ans : 0)

3. Value at j is incremented every time t1 and t2 contain unequal values. Hence, j keeps a *count of distinct elements* in the list.

2 votes

FOR ANSWER 1

Since every time the statement s1 will get executed so max n-1 comparisons

S2 willl be executed when statement s1 is true if all the element in list is same than 0 times s2 will be executed and n-1 times atmost

j is determining The Number of the pair which are not identical

Tell me if i am wrong

Since every time the statement s1 will get executed so max n-1 comparisons

S2 willl be executed when statement s1 is true if all the element in list is same than 0 times s2 will be executed and n-1 times atmost

j is determining The Number of the pair which are not identical

Tell me if i am wrong