# Summing 3 consecutive integers in a list to see if the sum matches a specified value

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>();
{
for (int i = 0; i < list.Length; 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
Console.WriteLine(a.ContainsSum3(69)); //True
}
}

• What is the point of the ToArray? You already have a list; just index into the list. Commented Oct 19, 2016 at 19:58
• 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. Commented Oct 19, 2016 at 20:01

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;

{
for (int i = 0; i < list.Length; 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];
_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
Console.WriteLine(a.ContainsSum3(69)); //True
}
}

• there is a hole starting _lastIndexed + 1. Add is enumerating anyway why not do it there. But nice overall approach. Commented Oct 19, 2016 at 20:54
• (1st answer indicating one can prepare a set of sums, which should speed follow-on queries.) Commented Oct 19, 2016 at 21:07
• 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. Commented Oct 20, 2016 at 8:56
• 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. Commented Oct 20, 2016 at 11:39

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;

• 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? Commented Oct 19, 2016 at 17:55
• How can you expect to sum that values without iterating the list? Commented Oct 19, 2016 at 18:00
• 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)? Commented Oct 19, 2016 at 18:24

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)
{
}
}

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

{
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 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

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];
}

{
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);
}

}


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);
}

{
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;
}

// Correct handling in case the passed list is empty!
if (sumFound) return true;

foreach (int n in list) {
}
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 };

}
}


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