0

Possible Duplicate:
checking if 2 numbers of array add up to I

My Problem is i have a given number no=10; assume and a Array A the i have to find those no who's difference is the given no.. Ex:- A[5]-A[3]=10; then Print print(A[5]); Print(A[5])
I have a algorithm that do it in O(n^2) time but we need something better...
My intuition is may be do something after Shorting the Array..... But How.. because after shorting it also need two loop to check that condition....
I am little bit confused ......

Community
  • 1
  • 1
Sumit Singh
  • 15,743
  • 6
  • 59
  • 89

1 Answers1

5

Original answer - O(n log n)

How about:

  • Sort the array (or a copy). This is O(n log n)
  • Iterate over the array, and for each value x do a binary search for x + no
    • Each binary search is O(log n)
    • Overall O(n log n)

Overall cost: O(n log n)

Modification to the above, as per Steve Jessop's comment:

FWIW, you don't have to do a binary search for x + no. As you iterate over the array, you can maintain a second iteration point in advance of the first one. Since the array is sorted, at each step x + no is greater than or equal to what x + no was in the previous step, so a linear search starting at the second iteration point from the previous step only ever goes forward and hence is O(n) total for the whole outer iteration, even though it isn't O(1) for each of the n steps.

This still requires a sort beforehand, which is O(n log n) though.

Best answer IMO (simple to implement and O(n))

EDIT: Or, of course, build a HashSet to make the containment check even quicker (assuming that creating the set is amortized O(n) and lookups are O(1)):

HashSet<int> values = new HashSet<int>(array);
foreach (int value in array)
{
    if (values.Contains(value + no))
    {
        // Found a match
    }
}
Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
  • 2
    Right, or use a Dictionary rather than a sorted array for O(n) – Polity Oct 20 '11 at 09:43
  • @Polity: True - doh! Will edit. – Jon Skeet Oct 20 '11 at 09:44
  • 1
    FWIW, you don't have to do a binary search for `x + no`. As you iterate over the array, you can maintain a second iteration point in advance of the first one. Since the array is sorted, at each step `x + no` is greater than or equal to what `x + no` was in the previous step, so a linear search starting at the second iteration point from the previous step only ever goes forward and hence is `O(n)` total for the whole outer iteration, even though it isn't `O(1)` for each of the `n` steps. Doesn't affect overall complexity *unless* you also claim an `O(n)` sort (radix or whatever). – Steve Jessop Oct 20 '11 at 09:51
  • @SteveJessop: Except you've still got O(n log n) from the sorting :) – Jon Skeet Oct 20 '11 at 09:52
  • Or using the first part of counting sort as described in http://stackoverflow.com/questions/4895405/checking-if-2-numbers-of-array-add-up-to-i/4906715#4906715 => O(n + k) – Lasse Espeholt Oct 20 '11 at 09:52
  • @Jon: agreed, I was just editing the comment to cover that, sorry. And regardless of complexity, I'm pretty sure that maintaining the second iteration point will be faster. – Steve Jessop Oct 20 '11 at 09:54
  • @lasseespeholt: That relies on the limited range part though. These approaches are more general :) – Jon Skeet Oct 20 '11 at 09:54
  • @JonSkeet Yes, but it is a solution which is the best in certain scenarios. And if this question is homework or an exercise, all solutions will contribute from my point of view. – Lasse Espeholt Oct 20 '11 at 09:57
  • @SteveJessop: Possibly. But that "fixed-width" can be 32-bits, making a radix sort somewhat impractical, assuming that's what you meant. And yes, I agree about the difference between O(n) and O(n log n). It might be interesting to benchmark these solutions in different situations some time... – Jon Skeet Oct 20 '11 at 10:03
  • @Jon: drat, I deleted my comment because I realised it was wrong (you don't actually need the hash function to be O(1), merely that hashing all of the data put together is O(n), same deal as my second iterator). You're too quick at this. Anyway, to anyone reading who was confused, the gist was that if the data is fixed-width (e.g. `int`), then sorting is possible in `O(n)`. As Jon says, though, that's not an especially useful `O(n)`, I think the big question for real performance is whether or not the sort beats any memory allocation and poor locality of the hashset. – Steve Jessop Oct 20 '11 at 10:07
  • @JonSkeet - solutions 2 and 3 are both linear, but I suspect that solution 2 is going to be significantly faster than solution 3. Creating a HashSet containing all of the numbers is a relatively expensive operation. – Stephen C Oct 20 '11 at 10:08