CODEWITHSUNDEEP
cfunction
Icestorm
Icestorm

Reputation: 197

C Library Find Difference Between Two Arrays

Given 2 arrays I need a C Function/Library that will find what's different between 2 arrays.

array1[] ={"a","b","c","e"}
array2[] ={"a","c","e"}

and the function should return

{"b"}

These 2 arrays are guaranteed to be sorted, but not the same size. I just need this function to be fast.

Upvotes: 0

Views: 1904

Answers (2)

Anshul garg
Anshul garg

Reputation: 233

@Oli Charlesworth

if arr1[]={"a","b","c"} and arr2[]={"d","e","f"}

in this case i guess ur logic will traverse elements of array(whichever is lower) but there is no need as by first comparsion only u can find the result hence result is possible for this case in o(1).....

Upvotes: 0

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

Here's an O(n) algorithm:

Create two pointers, each initialized to point at the first element of each array. Every time *p1 < *p2, add *p1 to the output array and increment p1. Same for p2. If they are equal, increment both.

I'll leave you to figure out how to handle duplicate elements, and what to do when one pointer reaches the end of its array.

[Also, if you're able to use C++, then you should just use std::set_symmetric_difference.]

Upvotes: 4

Related Questions