Take the 2-minute tour ×

Since the problem is long i can not describe it at title.

Imagine that we have 2 unsorted integer arrays. Both array lenght is n and they are containing interegers between 0 - n^765 (n power 765 maximum) .

I want to compare both arrays and find out whether they contain any same integer value or not with in O(n) time complexity.

no duplicates are possible in the same array

Any help and idea is appreciated.

share|improve this question
n^765? Thats a great number... –  erenon Dec 17 '10 at 12:24
yes. but do not stuck on numbers. i need the logic. the problem here is of course memory. otherwise there are too many memory consuming O(n) sorting algorithms. –  MonsterMMORPG Dec 17 '10 at 12:31
2 arrays can fit into memory - but 3 can't? –  flashnik Dec 17 '10 at 12:32
There are no array count limitation. but array sizes are very important. array lenght can not be equal to the biggest number. –  MonsterMMORPG Dec 17 '10 at 12:36
If the arrays have length n and the largest number is n^765 then an O(1) algorithm is (probably) sufficient: the likelihood that the 2 arrays contain the same number is vanishingly close to 0 for any n>1. –  High Performance Mark Dec 17 '10 at 13:00
show 3 more comments

4 Answers

up vote 1 down vote accepted

By assuming multiplication and division is O(1):

Think about numbers, you can write them as:

Number(i) = A0 * n^765 + A1 * n^764 + .... + A764 * n + A765.

for coding number to this format, you should just do Number / n^i, Number % n^i, if you precompute, n^1, n^2, n^3, ... it can be done in O(n * 765)=> O(n) for all numbers. precomputation of n^i, can be done in O(i) since i at most is 765 it's O(1) for all items.

Now you can write Numbers(i) as array: Nembers(i) = (A0, A1, ..., A765) and know you can radix sort items :

first compare all A765, then ...., All of Ai's are in the range 0..n so for comparing Ai's you can use Counting sort (Counting sort is O(n)), so your radix sort is O(n * 765) which is O(n).

After radix sort you have two sorted array and you can simply find one similar item in O(n) or use merge algorithm (like merge sort) to find most possible similarity (not just one).

for generalization if the size of input items is O(n^C) it can be sorted in O(n) (C is fix number). but because the overhead of this way of sortings are big, prefer to using quicksort and similar algorithms. Simple sample of this question can be found in Introduction to Algorithm book, which asks if the numbers are in range (0..n^2) how to sort them in O(n).

Edit: for clarifying how you can find similar items in 2-sorted lists:

You have 2 sorted list, for example in merge sort how do you can merge two sorted list to one list? you will move from start of list 1, and list 2, and move your head pointer of list1 while head(list(1)) > head(list(2)), and after that do this for list2 and ..., so if there is a similar item your algorithm will stop (before reach the end of lists), or in the end of two lists your algorithm will stop.

it's as easy as bellow:

public int FindSimilarityInSortedLists(List<int> list1, List<int> list2)
   int i = 0;
   int j = 0;

   while (i < list1.Count && j < list2.Count)
      if (list1[i] == list2[j])
         return list1[i];

      if (list1[i] < list2[j])
   return -1; // not found
share|improve this answer
this is the most logical answer. but numbers are not power of n. numbers are between 0 and n^765. for example a number can be n^765-1 or n^454-66 . at first i also thought similiar way to yours . but since numbers are not always power of n it fails. –  MonsterMMORPG Dec 17 '10 at 22:13
@PokemonCraft, I didn't said that numbers are pow of n I said you can write each number in "A0 * n^765 + A1 * n^764 + .... + A764 * n + A765" format, for example for n^765 -1 you have : A0 = 1, A765 = -1, Ai = 0 for others, or for n^454-66 you have A310 = 1, A0 = -66, Ai = 0 for others. –  Saeed Amiri Dec 18 '10 at 6:08
i did not understand how will i check whether they contain same value or not after sorting the way you suggested without increasing O(n) time complexity. –  MonsterMMORPG Dec 20 '10 at 11:43
@PokemonCraft, I'd updated my answer. –  Saeed Amiri Dec 21 '10 at 5:54
add comment

What you want is impossible. Each element will be stored in up to log(n^765) bits, which is O(log n). So simply reading the contents of both arrays will take O(n*logn).

If you have a constant upper bound on the value of each element, You can solve this in O(n) average time by storing the elements of one array in a hash table, and then checking if the elements of the other array are contained in it.


The solution you may be looking for is to use radix sort to sort your data, after which you can easily check for duplicate elements. You would look at your numbers in base n, and do 765 passes over your data. Each pass would use a bucket sort or counting sort to sort by a single digit (in base n). This process would take O(n) time in the worst case (assuming a constant upper bound on element size). Note that I doubt anyone would ever choose this over a hash table in practice.

share|improve this answer
it can be done with hashing method but i also need to have that hashing method. not just saying using hashing. so i have to explain what kind of hashing is used. –  MonsterMMORPG Dec 17 '10 at 12:40
do not care about bit size. i need the logic. –  MonsterMMORPG Dec 17 '10 at 12:45
@PokemonCraft: You can use pretty much any kind of hash table you want. Its size should be around 2*n. To save space, you can store pointers to the values in the hash table instead of the values themselves. –  interjay Dec 17 '10 at 13:11
As for your second comment: maybe you don't care about bit size, but bit size means that O(n) is impossible for the problem you described. –  interjay Dec 17 '10 at 13:13
@interjay, as you wrote in your first paragraph every iteration on a list of numbers within 0..n of size n takes O(nlog(n)), you changed the world :) so finding max item in the list of size n, and numbers within 0..n is O(nlog(n)) :) (n^765 can be coded in 765log(n) and n can be coded in log(n)), the main part of your false conclusion is there is no need to iterate over all bits. comparing items takes O(1) –  Saeed Amiri Dec 17 '10 at 15:56
show 1 more comment

If memory was unlimited you could simply create a hashtable with the integers as keys and the values the number of times they are found. Then to do your "fast" look up you simple query for an integer, discover if its contained within the hash table, and if found check that the value is 1 or 2. That would take O(n) to load and O(1) to query.

share|improve this answer
yes but unfortunately i do not have unlimited memory. –  MonsterMMORPG Dec 17 '10 at 12:41
@PokemonCraft: what are exactly your memory limitations? Certainly you can use O(n) memory, no? –  R. Martinho Fernandes Dec 17 '10 at 12:46
well actually there are no memory limitations. but the array size can not be biggest number in the given arrays . for example let the biggest number is 76^534 . the array size that we are going to use can not be equal to this number. because there are so many O(n) sorting algorithms with this way working. –  MonsterMMORPG Dec 17 '10 at 12:49
@PokemonCraft hashtables don't need to have space every possible item, just enough space so that items don't collide very often. A hash table of size 2-3 times bigger than n should be more than sufficient and still far less than n^765. –  MerickOWA Dec 17 '10 at 16:05
@PokemonCraft I don't completely understand your comment but... What I'm saying is that the input, i.e. the list of numbers, must be static in nature to guarantee that you're never going to get a collision. Otherwise it's impossible to guarantee that you're never going to be a collision. –  wheaties Dec 19 '10 at 3:29
show 6 more comments

I do not think you can do it O(n). You should check n values whether they are in the other array. This means you have n comparing operations at least if the other array has just 1 element. But as you have n element it the other array as well, you can do it just O(n*n)

share|improve this answer
You can do membership checks in ~O(1) time. Look up hash tables. –  R. Martinho Fernandes Dec 17 '10 at 12:35
well you can do it with O(n) time complexity for sure since it is asked from me to achive this. Also hash table is a good way but what kind of hash algorithm i can use. i have to also have an idea about hash algorithm . because it is also asked. hash algorithm for sure would solve the problem but it can not be a black box :) –  MonsterMMORPG Dec 17 '10 at 12:38
@Pokemon: "well you can do it with O(n) time complexity for sure since it is asked from me to achive this" Your reasoning is deeply flawed here. You are fortunate not having had the experience of dealing with professors who have zero clue what they are talking about. –  LeakyCode Dec 17 '10 at 12:41
Do not forget the cost of building a hash table –  HamoriZ Dec 17 '10 at 12:43
@ Mehrdad Afshari maybe it is unfortunate that you can not solve this kind of problem ^^. well this is possible with O(n) time complexity without having biggest number sized array. and i have to figure it out :) –  MonsterMMORPG Dec 17 '10 at 12:47
show 9 more comments

Your Answer


