Finding if sequential numbers for total exists

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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