Author |
Topic: Are two arrays are equal (Read 728 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Are two arrays are equal
« on: Jul 28th, 2010, 9:46am » |
 Quote  Modify
|
Given two arrays A, B of size n, find whether both arrays has same set of elements (order is not required)?
Example: A= {4, 1, 3} B= {3, 1, 4}, you should return true.
Sorting comparing two arrays is a trivial solution to this problem. Is there any faster or better way to solve this?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Are two arrays are equal
« Reply #1 on: Jul 28th, 2010, 9:55am » |
Quote Modify
|
Not really. You can find out a bit faster when they aren't the same though.
If you take quicksort as the basic mechanism, then when you partition both arrays around the same pivot, obviously the corresponding partitions need to be the same size; if they're not, then you can quit before finishing sorting.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sateesp
Newbie
Gender:
Posts: 35
|
|
Re: Are two arrays are equal
« Reply #2 on: Jul 28th, 2010, 10:05am » |
Quote Modify
|
But worst case it leads O(NLogN). Can we solve this O(N)?
| hidden: |
Just thinking, can we do something like this..
If (sum of all the elements in A = sum of all elements of B ) & ( product of of all the elements in A == product of all the elements in B)
return true.
|
|
|
IP Logged |
|
|
|
pex
Uberpuzzler
Gender:
Posts: 880
|
|
Re: Are two arrays are equal
« Reply #3 on: Jul 28th, 2010, 10:21am » |
Quote Modify
|
on Jul 28th, 2010, 10:05am, sateesp wrote:Just thinking, can we do something like this..
If (sum of all the elements in A = sum of all elements of B ) & ( product of of all the elements in A == product of all the elements in B)
return true. |
|
That only works if N=2. (Consider A={1,9,10}, B={2,3,15}.) In general, you'd need N equations to determine N unknowns - and they'd all need to be equations in all N elements (because order doesn't matter), so that would be O(N2).
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Are two arrays are equal
« Reply #4 on: Jul 28th, 2010, 1:17pm » |
Quote Modify
|
It can be done in amortized O(N) time with O(N) additional memory using a hash-based map or multi-set.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print