CODEWITHSUNDEEP
mathdata-structureslinked-list
Master shifu
Master shifu

Reputation: 19

Checking whether two lists are similar or not

In one of the examination, they asked us to write a function "int similar()" to check whether two list's data are similar or not irrespective of their order. they can also be of different sizes(in that case, they are dissimilar) that is,. 3->2->-1 and -1>3>2 are similar I wrote a program for that which is shown below. that is, for list one,I am adding all the elements and storing in sum1. I am multiplying all the elements and storing in product1. similarly , sum2 and product2 for 2nd list. if their sums and products are equal, then they must be containing same elements. my question is that is this algorithm complete? is there any case where my logic fails? please help me

 #include<stdio.h>
 struct _node_
 {
   int data;
   struct _node_ *ptr;
 };

 typedef struct _node_ Node;

struct _linkedlist_
 {
   Node *head;
   Node *tail;
   int count;
 };

 typedef struct _linkedlist_ List;

 int similar(List *, List *);

int main()
{

 //...code//

return 0;
}

int similar(List *one, List *two)
{
 int sum1=0;
 int sum2=0;
 int product1=1;
 int product2=1;
 int i;
 Node *temp;

 temp=one->head;
 for(i=0;i<one->count;i++)
{
 sum1=sum1+(temp->data);
 prodcut1=product1*(temp->data);
 temp=temp->ptr;
 }   

temp=two->head;
for(i=0;i<two->count;i++)
{
  sum2=sum2+(temp->data);
  prodcut2=product2*(temp->data);
  temp=temp->ptr;
 }  

if(sum1==sum2 && product1==product2)
  return 1;

 return0;
 }

Upvotes: 0

Views: 62

Answers (3)

Rory Daulton
Rory Daulton

Reputation: 22544

Your algorithm is not complete since your logic can fail. For your example 3->2->-1 there is another sequence that has the same sum and product but is not similar, namely

1 -> (3 + sqrt(33)) / 2 -> (3 - sqrt(33)) / 2

(Those values round to 1, 4.37228, and -1.37228.)

You can check and see that the sum of those values is 4 and the product is -6, just like your original list.

This happens because you put only two requirements on the values, which means you remove only two degrees of freedom. If the list has three or more values, that leaves one or more degrees of freedom, which allows for infinitely many possibilities. I showed you an example where the first value was 1--an example could be given for any value x where it is not true that -0.971168 < x <= 0 (approximately).

So you need another approach. You could sort each list then compare them. You could also put the values for each list into a multi-set (also called a bag or mset or counter) and compare those multi-sets.

Upvotes: 1

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1529

1. Sort both lists
2. Check every item of the list.
   2.1 if they are not equal
          -> print: lists are not equal.
3. lists are equal

Note: you either can sort the list, or make two separate lists, adding values in sorted order.

Upvotes: 0

work_ishaan
work_ishaan

Reputation: 354

As per the requirement mentioned in the question of the data being similar (i.e you are only checking for the order of data)

Consider a case where you have elements [-3,0,3] in list 1 and elements [10,-10,0] in the list 2.

In this case, the sum will be 0, and the product will also be 0

Upvotes: 0

Related Questions