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