1.2k views

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;
if (t1! = NULL)
t2 = t1 ->next;
*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;
}

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

1. How many times is the comparison in statement $S1$ made?
2. What is the minimum and the maximum number of times statements marked $S2$ get executed?
3. What is the significance of the value in the integer pointed to by $j$ when the function completes?
in DS
edited | 1.2k views
0

1. As we are comparing here pair wise so for $n$ elements we require compulsory  $n-1$ comparison
2. $S2$ is executed only for distinct elements so max $n-1$ times and min $0$ when all $r$ duplicates or list contain no or $1$ element.
3. $j$ holds the count on number of distinct elements in the ordered list.
by Boss (23.6k points)
edited by
0
Isn't assigning an integer value such as 1 to a pointer a bad way of doing things?
+2
*j=1 here * is  not representing pointer, but it is value at operator or Dereferencing operator.

1. n elements are compared n-1 times. Finding larger of 2 numbers is done in 1 comparison, for 3 in 2 comparisons and so on.  (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.

by Active (2.4k points)
edited

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
by (31 points)
0
Here Ur explanation of C is incorrect when there is only 1 node @ time
j should be 1 while ur ans saying abt pairs and when there is only one node there is 0 pairs.