Find if pair of elements with given sum exists in large integer array

Question

I'm having a integer array of 10 Million elements, how to write a function in C# which returns True if the array has a pair which sums up to 75.

My code is:

        int sum = 75, max = 10000000;
        int[] array = new int[max];
        bool checkFlag = false;
        Random rnd = new Random();
        Stopwatch sw = Stopwatch.StartNew();

        for (int i = 0; i < max; i++)
        {
            array[i] = rnd.Next(0, max * 20);
        }
        Array.Sort(array);
        if (array[0] + array[1] <= sum)
        {
            Console.WriteLine("{0} + {1} = {2}", array[0], array[1], array[0] + array[1]);
            checkFlag = true; 
        }
        Console.WriteLine("Sum upto 75 is: " + checkFlag);

Why do you have to do this? Is there any use for it or is it just a programming exercise? — Cyral
– Cyral, Commented Sep 18, 2014 at 23:39
This will take a long time via brute force search. What kind of time can this take? — BradleyDotNET
– BradleyDotNET, Commented Sep 18, 2014 at 23:40
@EdS. Knowing the reasoning behind something is good so we can provide better examples and advice for a specific problem. — Cyral
– Cyral, Commented Sep 18, 2014 at 23:41
This will take a long time any way. A lot less if the array contain only positive elements (since you can first filter only those <= 75). — Mephy
– Mephy, Commented Sep 18, 2014 at 23:42

Hans Passant · Accepted Answer · 2014-09-19 00:32:52Z

8

This is a bucketing problem. You want buckets of 0s to pair with 75s, 1s to pair with 74s, etcetera. Bucketing is a Dictionary jobby. A Dictionary<int, List<int>> gives you a result in O(n) amortized. If you only care about a bool result then a HashSet<int> is good enough. You can't get better than O(n).

    static bool PairExists(int[] arr, int sum) {
        var set = new HashSet<int>();
        foreach (int elem in arr) set.Add(elem);
        foreach (int elem in set)
            if (set.Contains(sum - elem)) return true;
        return false;
    }

If the array is likely to contain the pair then you could consider testing after the Add() call, still O(n).

edited Sep 19, 2014 at 0:32

answered Sep 19, 2014 at 0:17

Hans Passant

946k151 gold badges1.8k silver badges2.6k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Hans Passant Over a year ago

The for loops makes it O(n). The HashSet operations are O(1).

Colin Pear Over a year ago

HashSet operations are at best O(1) if there are no collisions. O(N) if not. Depends on the hash algorithm.

user2864740 · Accepted Answer · 2014-09-19 00:15:11Z

This will work if the array is sorted.

public bool ContainsPair(int[] array) 
{
    int i = 0;
    int j = array.Length - 1;
    while(i < j)
    {
        if (array[i] + array[j] == 75) 
            return true;
        else if (array[i] + array[j] <  75) 
            i++;
        else if (array[i] + array[j] >  75) 
            j--;
    }
    return false;
}

You use two pointers and walk towards the middle of the array. Pointer i starts at the beginning of the array, while j starts at the end. If you find two numbers that sum up to 75, you return true. If the sum is less than 75, then you move pointer i one step towards the middle and check again. If the sum is more than 75, you move pointer j one step towards the middle and check again.

If the two pointers meet, then you return false, because no pair was found.

This is O(n), not including sorting the array.

Reactgular · Accepted Answer · 2014-09-19 00:05:05Z

0

You can do a brute force search.

public bool hasPairOf(int[] a, int sum)
{
   for(int i=0; i < a.length-1; i++)
   {
      if(a[i]+a[i+1] == sum)
         return true;
   }
   return false;
}

Alternatively, you could create an enumerator and use LINQ.

public static IEnumerate<int> toSums(this int[] a)
{
   for(int i=0; i < a.length-1; i++)
   {
      yield return a[i]+a[i+1];
   }
}

Now you can do the following.

a.toSums().Any(pair=>pair == 75);

Both should have the same performance. If you ask why? that's because C# will only execute the enumerator until the Any condition is true. The toSums function uses the yield keyword to create an enumerator that is only executed when it is evaluated.

EDIT:

To find any pair of values in an array that sum to 75 and not just adjacent. I would do it using nothing but LINQ for easier reading.

function bool hasPairOf(int[] a, int sum)
{
    var nums = a.Where(val=>val <= sum)
                .Select((v,i)=>new{value=v,index=i})
                .ToArray();

    return (from a1 in nums
            from a2 in nums
            where a1.index != a2.index
                  && a1.value+a2.value == sum
            select true).FirstOrDefault();
}

edited Sep 19, 2014 at 0:05

answered Sep 18, 2014 at 23:50

Reactgular

55.1k24 gold badges175 silver badges219 bronze badges

4 Comments

BradleyDotNET Over a year ago

Not quite, he never said the elements had to be sequential. This is the approach I was going to take though.

user2864740 Over a year ago

This only check adjacent pairs, which is still O(n) .. but doesn't work without further restrictions.

Reactgular Over a year ago

oh! Any pair! Ah. That is a different story.

BradleyDotNET Over a year ago

@MathewFoscarini Not too bad, but you have increased the execution time by doing the "ToArray" first (especially if all the numbers are <= 75). "Brute force" should just do the self join (or a nested for loop, which is what I would have done) for "maximum" speed (even though it will still be quite slow).

zumalifeguard · Accepted Answer · 2014-09-19 00:17:52Z

0

If you can assume the numbers are positive, you can do this:

Create a boolean array of 75 elements.
Walk the list of 10,000,000 items. When you see one that's 75 or less:
- check to see boolean arry has an entry at element 75 - that number. If it does, you found a match.
- otherwise, set the nth entry of the boolean array.

Example C#:

        var bits = new bool[75];
        foreach (var n in intArray)
        {
            if (n <= 75)
            {
                var diff = 75 - n;
                if (bits[diff - 1])
                {
                    MessageBox.Show(string.Format("Found pair: {0} and {1}", n, diff));
                    break;
                }
                bits[n - 1] = true;
            }
        }

But if the numbers in the array can be any valid integer, including negative numbers, you can do something like this:

        var set = new HashSet<int>();
        foreach (var n in intArray)
        {
            if (n <= 75)
            {
                var diff = 75 - n;

                if (set.Contains(diff))
                {
                    MessageBox.Show(string.Format("Found pair: {0} and {1}", n, diff));
                    break;
                }
                set.Add(n);
            }
        }

edited Sep 19, 2014 at 0:17

answered Sep 18, 2014 at 23:47

zumalifeguard

9,0975 gold badges50 silver badges61 bronze badges

1 Comment

user2864740 Over a year ago

This trivially breaks down without further limits. What if there are values -200 and +275?

Fredou · Accepted Answer · 2014-09-19 00:24:43Z

using System;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            const int max = 10000000;
            const int sum = 75;

            var data = new int[max];

            var rnd = new Random();

            bool found = false; 
            int c = 1;
            Stopwatch sw;

            while (!found)
            {
                sw = Stopwatch.StartNew();
                for (int i = 0; i < max; ++i)
                {
                    data[i] = rnd.Next(0, max*25);
                }
                sw.Stop();
                Console.WriteLine("Took {0}ms to create the array", sw.ElapsedMilliseconds);

                sw = Stopwatch.StartNew();
                var check75 = new HashSet<int>(data.Where(x => x <= 75));
                sw.Stop();
                Console.WriteLine("Took {0}ms to create the hashset", sw.ElapsedMilliseconds);

                sw = Stopwatch.StartNew();
                for (int i = 0; i < max; ++i)
                {
                    if (check75.Contains(sum - data[i]))
                    {
                        Console.WriteLine("{0}, {1} ", i, data[i]);
                        found = true;
                    }
                }
                sw.Stop();
                Console.WriteLine("Took {0}ms to check75", sw.ElapsedMilliseconds);

                Console.WriteLine("Loop #" + c++);
            }
            Console.WriteLine("Finish");
            Console.ReadKey();
        }
    }
}

Sumit Thomas · Accepted Answer · 2021-11-09 04:06:19Z

0

Add the compliment of the sum in a Dictionary, if it doesn't have it. If dictionary already has the compliment then a pair exists for the given sum.

    public bool HasPair(List<int> arr, int sum)
    {
        var track = new Dictionary<int, int>();
        for (var i = 0; i < arr.Count; i++)
        {
            if (track.ContainsKey(arr[i]))
                return true;
            
            track.Add(sum - arr[i], arr[i]);
        }
        return false;
    }

answered Nov 9, 2021 at 4:06

Sumit Thomas

1

Collectives™ on Stack Overflow

Find if pair of elements with given sum exists in large integer array

6 Answers 6

2 Comments

Comments

4 Comments

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

Comments

4 Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related