2
\$\begingroup\$

I have a program where users can add integers to a list and then I want to check the list to see if any three consecutive integers in the list sum to a specified value. I have been told that it is taking too long when ran with a large number of integers in the list. The timing test that I am not passing is based upon looking for the first match of the sum of 3 consecutive integers, in a large list of integers, to one specific value. The specific value can vary with each run but not within the run and the single run is that is being timed.

class Aggro
{    
    private List<int> _numbers = new List<int>();
    public void AddToList(int[] list)
    {
        for (int i = 0; i < list.Length; i++ )
        {
            _numbers.Add(list[i]);
        }
    }

    public bool SumExists(int sum)
    {
        int[] numbers = _numbers.ToArray();
        for (int i = 0; i < numbers.Length -2; i++)
       {
            if (numbers[i] + numbers[i + 1] + numbers[i + 2] == sum)
            {
                return true;
            }
        }
        return false;
    }

    public static void Main(string[] args)
    {
        Aggro a = new Aggro();
        a.AddToList(new int[] { 12, 21, 16, 4, 67, 1 });
        Console.WriteLine(a.SumExists(41)); // True
        Console.WriteLine(s.SumExists(69)); // False
        a.AddToList(new int[] { 1 });
        Console.WriteLine(a.ContainsSum3(69)); //True
    }
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ What is the point of the ToArray? You already have a list; just index into the list. \$\endgroup\$ Commented Oct 19, 2016 at 19:58
  • 2
    \$\begingroup\$ What exactly is being timed? For example, could you do the following: obtain the array, compute every sum of three consecutive integers, put those into a set, and then when you are asked "is such-and-such a sum present?" you simply check the set. Creating the set is order n, but doing the lookup is order 1. \$\endgroup\$ Commented Oct 19, 2016 at 20:01

5 Answers 5

1
\$\begingroup\$

About performance:

One call of a.AddToList plus one call of a.SumExists cannot work conceptually faster than your variant. But several calls of a.AddToList plus several calls of a.SumExists can run much faster.

  1. You can index all the sums after first call to a.SumExists with as HashSet, so all other calls of SumExists will be run in \$O(1)\$.

  2. A second (and others) call to a.AddToList needs no recalc the whole index - you need only add new elements.

class Aggro
{    
    List<int> _numbers = new List<int>();
    HashSet<int> _index = new HashSet<int>();
    int _lastIndexed = -1;

    public void AddToList(int[] list)
    {
        for (int i = 0; i < list.Length; i++ )
        {
            _numbers.Add(list[i]);
        }
    }

    public bool SumExists(int sum)
    {
       if (_lastIndexed > -1 && _index.Contains(sum)) return true;
       for (int i = _lastIndexed + 1, c = numbers.Length - 2; i < c; i++)
       {
            int tmp = numbers[i] + numbers[i + 1] + numbers[i + 2];
            _index.Add(tmp);
            _lastIndexed = i;
            if (tmp == sum)  return true;
        }
        return false;
    }

    public static void Main(string[] args)
    {
        Aggro a = new Aggro();
        a.AddToList(new int[] { 12, 21, 16, 4, 67, 1 });
        Console.WriteLine(a.SumExists(41)); // True
        Console.WriteLine(s.SumExists(69)); // False
        a.AddToList(new int[] { 1 });
        Console.WriteLine(a.ContainsSum3(69)); //True
    }
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ there is a hole starting _lastIndexed + 1. Add is enumerating anyway why not do it there. But nice overall approach. \$\endgroup\$
    – paparazzo
    Commented Oct 19, 2016 at 20:54
  • \$\begingroup\$ (1st answer indicating one can prepare a set of sums, which should speed follow-on queries.) \$\endgroup\$
    – greybeard
    Commented Oct 19, 2016 at 21:07
  • \$\begingroup\$ Reaching amortized \$O(1)\$ run time on SumExists() is interesting. Well, that is if you actually did. It only becomes \$O(1)\$ when averaged over at least \$n\$ invocations. Plus, that index means you are now also stuck in \$O(n)\$ space complexity for good. It would be a good solution though, if the problem description wouldn't explicitly state that only a single sum will ever be sampled per run. \$\endgroup\$
    – Ext3h
    Commented Oct 20, 2016 at 8:56
  • \$\begingroup\$ Yes, it seems like I've missed important condition, and if a target sum is really static per run, it is obvious that there is no need for full index or index at all. But class usage example a little bit conflicting with that condition, so I 'd like author clarify the things. \$\endgroup\$
    – Buran
    Commented Oct 20, 2016 at 11:39
0
\$\begingroup\$

Why are you letting it go to i < numbers.Length?

You can access a List by position
Making a an array is not necessary

This is going to be O(n) - not going to make it much faster that I can think of

   for (int i = 0; i < _numbers.Length - 2; i++)
   {
        if (_numbers[i] + _numbers[i + 1] + _numbers[i + 2] == sum)
        {
            return true;
        }
    }
    return false;
\$\endgroup\$
3
  • \$\begingroup\$ Paparazzi - a) It is returning as soon at it hits a match. b) Thanks for that tip, however, I removed the convert to array code and directly referenced the list by position as you indicated and it is still failing the timing test. c) Is there an algorithm I am missing that would do this type of sum check without iterating the list? \$\endgroup\$
    – Dave Adler
    Commented Oct 19, 2016 at 17:55
  • \$\begingroup\$ How can you expect to sum that values without iterating the list? \$\endgroup\$
    – paparazzo
    Commented Oct 19, 2016 at 18:00
  • 2
    \$\begingroup\$ How (and why) can we guess why it is still failing the timing test while still only given clues (in the form of calls in main()) as to what will be required? And why bother to solve something not specified sufficient (yet)? \$\endgroup\$
    – greybeard
    Commented Oct 19, 2016 at 18:24
0
\$\begingroup\$

Really you only have two approaches - iteration, or precomputation. There have been some other examples of precomputation here, but I'll throw one more into the mix - computing the sums at the time each element is added/removed from the collection. You'd need a custom collection type - here basically everything except .Add, .Remove, and .Clear just call into the list's implementation.

Add is quite straightforward, we added a new item and it becomes part of a new triplet. Remove is slightly trickier as we have to remove three precomputed values and recalculate two of them.

A Dictionary is used to count the number of triplets summing to a particular value, so that we can remove the key only when every possible triplet summing to that value is gone. I chose to do the bounds checking within the sum method itself but that could be done elsewhere.

public class SummedCollection : ICollection<int>
{
    private List<int> _members = new List<int>();
    private Dictionary<int, int> _sumCounts = new Dictionary<int, int>();

    public SummedCollection()
    {
    }

    public SummedCollection(IEnumerable<int> sequence)
    {
        foreach (int x in sequence)
        {
            Add(x);
        }
    }


    public int Count
    {
        get { return _members.Count;}
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public void Clear()
    {
        _members.Clear();
        _sumCounts.Clear();
    }

    public bool Contains(int item)
    {
        return _members.Contains(item);
    }

    public void CopyTo(int[] array, int arrayIndex)
    {
        _members.CopyTo(array, arrayIndex);
    }

    public IEnumerator<int> GetEnumerator()
    {
        return _members.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return _members.GetEnumerator();
    }

    public void Add(int item)
    {
        _members.Add(item);
        AddSumFrom(Count - 3);
    }

    public bool Remove(int item)
    {
        int index = _members.FindIndex(x => x == item);
        if (index == -1) { return false; }

        // Remove the calculated sums that this element participated in
        RemoveSumFrom(index - 2);
        RemoveSumFrom(index - 1);
        RemoveSumFrom(index);

        // Remove the element
        _members.RemoveAt(index);

        // Recalculate the sums for the now-changed triplets preceding the removal
        AddSumFrom(index - 2);
        AddSumFrom(index - 1);

        return true;
    }

    private int? SumFrom(int index)
    {
        if (index < 0 || index + 2 >= _members.Count) { return null; }
        return _members[index] + _members[index + 1] + _members[index + 2];
    }

    private void AddSumFrom(int index)
    {
        int? sum = SumFrom(index);
        if (sum == null) { return; }

        if (!_sumCounts.ContainsKey(sum.Value))
        {
            _sumCounts[sum.Value] = 1;
        }
        else
        { 
            _sumCounts[sum.Value]++;
        }
    }

    private void RemoveSumFrom(int index)
    {
        int? sum = SumFrom(index);
        if (sum == null) { return; }

        _sumCounts[sum.Value]--;
        if (_sumCounts[sum.Value] < 1)
        {
            _sumCounts.Remove(sum.Value);
        }

    }

    public bool ContainsSum(int sum)
    {
        return _sumCounts.ContainsKey(sum);
    }

}
\$\endgroup\$
0
\$\begingroup\$

The specific value can vary with each run but not within the run and the single run is that is being timed.

That information is key to solving this challenge.

Saying that the target sum can't change, is identical to saying that if the sum wasn't found up to now, none of the elements except for the last 3 need to be considered ever again.

Your current implementation runs the sum test again every time a different sum is queried, which needs to happen every time a set of fresh summands has been added. This results in an effective run time of \$O(n^2)\$ for single value additions.

However, by checking each possible sum only exactly once, you can lower the run time cost down to \$O(n)\$. In the best case, you can even discard all further input for the same run, once the expected sum has been found.

You don't need to hold the entire list of previously entered numbers in memory for that either. All you need to remember, is the sum of the last 3 inputs, as well as the inputs themselves so you can recompute / update the current sum accordingly. For remembering the last few inputs you can simply use a Queue, it's specifically made for such scenarios.

This allows you to drop the memory footprint from \$O(n)\$ to \$O(1)\$ as well.

If you want to express it with OOP, you can now just encapsulate each run in a SlidingSum object of its own, and you are done.


What it ultimately looks like:

class SlidingSum {
    // Targets
    int summands;
    int targetSum;

    // State
    Queue<int> partialSummands;
    int partialSum = 0;
    bool sumFound = false;

    public SlidingSum(int targetSum, int summands) {
        this.summands = summands;
        this.targetSum = targetSum;
        partialSummands = new Queue<int>(summands);
    }

    public bool AddSummand(int n)
    {
        if (sumFound) return true;

        // Test if sum has the minimal number of summands yet
        if(partialSummands.Count() >= summands ) {
            partialSum -= partialSummands.Dequeue();
        }

        // Increment partial sum
        partialSum += n;
        partialSummands.Enqueue(n);

        // Test for target sum
        if (partialSummands.Count() == summands && partialSum == targetSum) {
            sumFound = true;
            return true;
        }

        return false;
    }

    public bool AddSummand(int[] list) {
        // Correct handling in case the passed list is empty!
        if (sumFound) return true;

        foreach (int n in list) {
            if (AddSummand(n)) return true;
        }
        return false;
    }

    public bool SumExists() {
        return sumFound;
    }
}

class Program
{
    public static void Main(string[] args)
    {
        SlidingSum runA = new SlidingSum(41, 3);
        SlidingSum runB = new SlidingSum(69, 3);
        int[] x = new int[] { 12, 21, 16, 4, 67, 1 };

        Console.WriteLine(runA.AddSummand(x)); // True
        Console.WriteLine(runB.AddSummand(x)); // False

        Console.WriteLine(runA.AddSummand(1)); // Still True
        Console.WriteLine(runB.AddSummand(1)); // True
    }
}
\$\endgroup\$
0
\$\begingroup\$

It seems to me that within a specific run, once you have found the sum you're looking for, it doesn't matter what numbers are added the result will always be true. So if you use a rolling sum and a couple of bool variables you can shorten your time considerably:

class Aggro
{
    private static int testSum = 0;
    private static bool firstRun = true;
    private static bool trueRun = false;
    public static void Initialize()
    {
        testSum = 0;
        firstRun = true;
        trueRun = false;
    }
    public static bool SumExists2(int sum, List<int> numbers)
    {
        if(firstRun)
        {
            firstRun = false;
            testSum = numbers.Take(3).Sum();
            if (testSum == sum)
            {
                trueRun = true;
                return true;
            }
            for (int i = 3; i < numbers.Count; i++)
            {
                testSum += numbers[i] - numbers[i - 3];
                if (testSum == sum)
                {
                    trueRun = true;
                    return true;
                }
            }
        }
        else if(!trueRun)
        {
            testSum += numbers.Last() - numbers[numbers.Count - 4];
            if(testSum == sum)
            {
                trueRun = true;
                return true;
            }
        }
        else
        {
            return true;
        }
        return false;
    }
    public static void Main(string[] args)
    {
        List<int> testArray = new List<int>(new int[] { 12, 21, 16, 4, 67, 1 });
        Initialize();
        Console.WriteLine(SumExists2(41, testArray)); // True
        Initialize();
        Console.WriteLine(SumExists2(69, testArray)); // False
        testArray.Add(1);
        Console.WriteLine(SumExists2(69, testArray)); //True
        return;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Using a rolling sum to substitute one subtract for one add. What is the idea with the static class variables? \$\endgroup\$
    – greybeard
    Commented Oct 20, 2016 at 18:20
  • \$\begingroup\$ @greybeard - A rolling sum means that you don't have to iterate over the whole collection each time a new number is added. TestSum holds the rolling sum from one test to the next. firstRun restricts iteration to only the first run through for each new target sum. trueRun shortcuts the code once the list contains a true combination. \$\endgroup\$
    – user33306
    Commented Oct 20, 2016 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.