Author |
Topic: How to find subset in two a array (Read 1155 times) |
|
nks
Junior Member
Gender: 
Posts: 145
|
 |
How to find subset in two a array
« on: Aug 26th, 2011, 10:48am » |
 Quote  Modify
|
There are two arrays given N and M(larger). How to find wether N is subset of M, i.e All elements of N is available in M,
No hashing is to be used.
Is there any other way possible without using any extra array in O(N).
|
| « Last Edit: Aug 27th, 2011, 9:10am by nks » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: How to find subset in two a array
« Reply #1 on: Aug 26th, 2011, 11:41am » |
Quote Modify
|
If M is smaller than N, as you stated, then N can't be a (proper) subset of M.
Assuming that was just a mistake, you could find whether the smaller set is a subset of the larger one in linear time if they're both sorted.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: How to find subset in two a array
« Reply #2 on: Aug 27th, 2011, 9:16am » |
Quote Modify
|
Thanks TOWR for correction, Have corrected it, M is larger,
Sorting is known as O( N log N) excluding counting sort.
looking in O(N) with space O(1).
|
| « Last Edit: Aug 27th, 2011, 9:17am by nks » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: How to find subset in two a array
« Reply #4 on: Sep 12th, 2011, 12:05pm » |
Quote Modify
|
Define encodding of array elements by positive integers (injection), map positive integer i to i-th prime (of precomputed subset of primes) (injection as well). Make products \PiN and \PiM of compound injections of arrray elements of N and of M.
Find their greatest common divisor. If it equals to \PiN you are done.
This solves problem when elements of N must be in M with their full multicity.
Yes, I am joking with infinit precision arithmetic with O(1) per operation.
|
| « Last Edit: Sep 12th, 2011, 12:08pm by Hippo » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: How to find subset in two a array
« Reply #5 on: Sep 12th, 2011, 12:16pm » |
Quote Modify
|
Sort the smaller array. Go over the larger array and check into the smaller array using binary search. This should be M log N. If N <<< M, the sorting cost and the logN search cost should be sufficiently small enough.
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print