# Finding if sequential numbers for total exists

Question: Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T

Example:

A = [23, 5, 4, 7, 2, 11], T = 20: True because 7 + 2 + 11 = 20
A = [1, 3, 5, 23, 2], T = 8: True because 3 + 5 = 8
A = [1, 3, 5, 23, 2], T = 7: False because no sequence in this array adds up to 7

Write code to find if sequential numbers for total exists.

Note: I'm looking for an O(N) solution. There is an obvious O(N^2) solution but is not the final solution I'm looking for.

My answer code (in ruby) is the following. Please let me know if there is a more efficient way.

class Sequence
def initialize(integers)
@integers = integers
end

def continuous_sequence_for_total_exists?(total)
sliced_array = slice_array(total)
sliced_array.each do |array|
array.each do
if array.reduce(:+) == total
return true
else
array.shift
end
end
end

return false
end

private

# Slice array with any integer larger than max
#
# e.g.:
# [1, 3, 5, 23, 2] => [1, 3, 5], [2]
def slice_array(max)
chunks = @integers.chunk{ |i| i < max || nil }
chunks.map{ |answer, value| value }
end
end


## 3 Answers

Your code incorrectly returns false if I give it [23, 5, 4, 7, 2, 11, 1] and a target value of 20. The answer should still be 7 + 2 + 11, but it doesn't find it.

That's because the reduce operation always runs to the end of the array, so it is unable to pick out a matching sub-sequence in the middle of a larger sequence. It can only find it, if it's at the end. I.e. it does this:

5 + 4 + 7 + 2 + 11 + 1 => 30
4 + 7 + 2 + 11 + 1     => 25
7 + 2 + 11 + 1         => 21
2 + 11 + 1             => 13 # could just give up here, really
11 + 1                 => 12
1                      => 1

=> false


However 2 + 7 + 11 would've been a valid answer.

Your example input just happens to be crafted so that you get correct results; the matching sub-sequences are always anchored to the end of an array. They're never in the middle of it.

Furthermore, by chunking using i < max you remove values that are equal to the target sum. I.e. trying [1, 3, 7, 5, 23, 2] with a target of 7 will fail, even though there is a sequence - a sequence of 1 value - that matches.

This is however easily fixed by changing the block to use i <= max.

Overall, I'd propose something like this:

def sub_sequence_equal_to?(total, values)
sequences = values.chunk { |n| n <= total || nil }.map(&:last)

sequences.each do |sequence|
sequence.reduce(0) do |sum, n|
sum += n
sum -= sequence.shift while sum > total
return true if sum == total
sum
end
end

false
end


It'll gradually build a sum, but also subtract the earliest values if said sum has grown too large.

So given [23, 5, 4, 7, 2, 11, 1] and a target value of 20 it'll do something like:

5                  => 5
5 + 4              => 9
5 + 4 + 7          => 16
5 + 4 + 7 + 2      => 18
5 + 4 + 7 + 2 + 11 => 29
4 + 7 + 2 + 11 => 24
7 + 2 + 11 => 20

=> true


It's not quite $O(n)$, and perhaps there's a smarter way (it'd be nice to get rid of that separate chunk step for instance). Still, it's more efficient (and works better) than the original.

• Is this chunking step needed? What about just doing this? On another note, I always feel a little dirty mixing a nasty imperative while loop into my pristine functional methods... is there any way to solve this in a purely functional way without changing the big-O runtime? – Jonah Jan 2 '16 at 2:52
• @Jonah Yeah, it's not brilliant code. I tried a few ways to get rid of the chunking, but didn't find one I liked enough to post. The one you linked is nice, though I'm not a fan of blocks with side-effects (I tried one with each_with_object, to keep in contained, but it wasn't pretty). Of the solutions here, I like tokland's recursive one the best, overall – Flambino Jan 8 '16 at 20:21

As others have pointed out, your solution is O(n^2), chunk is not the right abstraction to use here. A O(n) solution for enumerables would involve linked lists and double-ended queues (with O(1) head/tail insertion/removal operations), but those data-structures are not implemented in the core, so it would require extra infrastructure (immutable-ruby).

However, if the input is always an array, you can use start/end indexes to reference the sliding window. It's O(n) time, O(1) space, functional, tail-recursive:

def cons_sum_equals?(xs, sum, win_start = 0, win_end = 0, win_sum = 0)
case
when win_sum == sum
true
when win_start == xs.size
false
when win_end == xs.size, win_sum > sum
cons_sum_equals?(xs, sum, win_start + 1, win_end, win_sum - xs[win_start])
else
cons_sum_equals?(xs, sum, win_start, win_end + 1, win_sum + xs[win_end])
end
end

cons_sum_equals?([23, 5, 4, 7, 2, 11, 1], 20) #=> true


Caveat: The previous code is kept simple for demonstration purposes. Sadly, tail-call optimization in CRuby is fairly limited and, to make it work for large inputs, you should: 1) change the cases for ifs. 2) join the last two cons_sum_equals? calls into one.

• I'm not sure shortening “consecutive” to “cons” is the right call here. “Cons” usually means “constant”, so it's a bit confusing. – Morgen Dec 27 '15 at 22:37
• I named it after each_cons, which means "each_consecutive". In Ruby, constant is usually shorten as "const" (const_get, const_set, ...). Anyway, it may be clear with "consecutive", yes. – tokland Dec 27 '15 at 22:44
• Ahh, tripped up by language specific conventions, my bad! – Morgen Dec 27 '15 at 22:50

Unfortunately, this is still $O(n^2)$.

It's a nice optimization to cull impossible values, but #reduce still iterates over the rest of the array, and that still happens once per potentially valid index.

One way to do this in $O(n)$ is to work with a sliding window. This is the approach taken in this version (which also fixes the bug noted by @Flambino).

#!/usr/bin/env ruby
class Sequence
def initialize(integers)
@integers = integers
end

def continuous_sequence_for_total_exists?(total)
check_array([], 0, total, @integers)
end

private

def check_array(window, total, target, source)
empty_source = source.nil? || source.empty?
empty_window = window.nil? || window.empty?
return false if empty_source && (total < target || empty_window)

# As an optimization, return true if the next element in source is a match
# all by itself. This would be caught by the rest of the algorithm, but this
# skips the calls that would do nothing but shrink the window until it is
# empty.
return true if total == target || source.first == target

if total > target
return check_array(window[1..-1], total - window.first, target, source)

elsif !empty_source && source.first > target
# We can optimize away some bad sequences by dropping the current window
# and the first element in source if it is larger than target. That value
# alone is sufficient to invalidate these sequences.
return check_array([], 0, target, source[1..-1])
else
return check_array(window + [source.first], total + source.first, target, source[1..-1])
end
end
end

Test = Struct.new(:array, :total, :expected)

[
Test.new([23, 5, 4, 7, 2, 11], 20, true),
Test.new([1, 3, 5, 23, 2], 8, true),
Test.new([1, 3, 5, 23, 2], 7, false),
Test.new([1, 3, 5, 23, 2], 1, true),
Test.new([1, 3, 5, 23, 2], 4, true),
Test.new([23, 5, 4, 7, 2, 11, 1], 20, true)
].each do | test |
actual = Sequence.new(test.array).continuous_sequence_for_total_exists?(test.total)
unless test.expected == actual
printf("Expected %s for %2d in %s, but was %s\n", test.expected, test.total, test.array, actual)
throw RuntimeError
end
end


This also includes a pattern you can use for writing simple test cases for algorithms you are playing with, but don't want to write a full project just to test.

This not perfect, as I've been doing quite a bit of work in Scala lately, which has nice facilities for optimizing tail-recursive functions. However, this should get you started on the road to an idiomatic Ruby solution, probably a loop of some sort.

There are two optimizations in this that are worth calling out.

The first is that, any value that is exactly equal to the target triggers an immediate return. This skips some wasted iterations, for example:

window = []        total = 0  target = 4  source = [1,1,1,4]
window = [1]       total = 1  target = 4  source = [1,1,4]
window = [1,1]     total = 2  target = 4  source = [1,4]
window = [1,1,1]   total = 3  target = 4  source = [4] # Optimization returns true here
window = [1,1,1,4] total = 7  target = 4  source = []
window = [1,1,4]   total = 6  target = 4  source = []
window = [1,4]     total = 5  target = 4  source = []
window = [4]       total = 4  target = 4  source = []  # Returns true


The second incorporates the optimization in the OP using #chunk, but does it as part of the single pass through the array. For example:

window = []      total = 0  target = 4  source = [3,2,1,8,1,2,1,5]
window = [3]     total = 1  target = 4  source = [2,1,8,1,2,1,5]
window = [3,2]   total = 3  target = 4  source = [1,8,1,2,1,5]
window = [3,2,1] total = 6  target = 4  source = [8,1,2,1,5]
window = [2,1]   total = 3  target = 4  source = [8,1,2,1,5]

# Skipped: window = [2,1,8] total = 11  target = 4  source = [1,2,1,5]
# Skipped: window = [1,8]   total = 9  target = 4  source = [1,2,1,5]
# Skipped: window = [8]     total = 8  target = 4  source = [1,2,1,5]

window = []      total = 0  target = 4  source = [1,2,1,5]
window = [1]     total = 1  target = 4  source = [2,1,5]
window = [1,2]   total = 3  target = 4  source = [1,5]
window = [1,2,1] total = 3  target = 4  source = [5] # Returns true