Log In
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) 
            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.

  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 by
Please explain...

3 Answers

24 votes
Best answer
  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.

edited by
Isn't assigning an integer value such as 1 to a pointer a bad way of doing things?
*j=1 here * is  not representing pointer, but it is value at operator or Dereferencing operator.
7 votes

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.

edited by
2 votes

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
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.
(n≥2) condition given in question

Related questions

26 votes
5 answers
The concatenation of two lists is to be performed on $O(1)$ time. Which of the following implementations of a list should be used? Singly linked list Doubly linked list Circular doubly linked list Array implementation of list
asked Sep 29, 2014 in DS Kathleen 6.1k views
17 votes
2 answers
An array $A$ contains $n \geq 1$ positive integers in the locations $A[1], A[2], \dots A[n]$. The following program fragment prints the length of a shortest sequence of consecutive elements of $A$, $A[i], A[i+1], \dots,A[j]$ such that the sum of their values is $\geq M$, a given positive ... +1; sum:= ◻ end else begin if(j-i) < min then min:=j-i; sum:=sum -A[i]; i:=i+1; end writeln (min +1); end.
asked Sep 29, 2014 in DS Kathleen 1.5k views
16 votes
3 answers
A size-balanced binary tree is a binary tree in which for every node the difference between the number of nodes in the left and right subtree is at most $1$. The distance of a node from the root is the length of the path from the root to the node. The height of a ... tree of height $h \geqslant 1$, how many nodes are at distance $h-1$ from the root? Write only the answer without any explanations.
asked Sep 29, 2014 in DS Kathleen 1.6k views
33 votes
6 answers
Consider a hash table with $n$ buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ ... has occurred in any of the $K$ insertions? What is the probability that the first collision occurs at the $K^{th}$ insertion?
asked Sep 29, 2014 in DS Kathleen 3.8k views