Return to 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:

[23, 5, 4, 7, 2, 11], 20: True because 7 + 2 + 11 = 20
[1, 3, 5, 23, 2], 8: True because 3 + 5 = 8
[1, 3, 5, 23, 2], 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

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

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 [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 [1, 3, 5, 23, 2], 7 Return 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

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:

[23, 5, 4, 7, 2, 11], 20: True because 7 + 2 + 11 = 20 
[1, 3, 5, 23, 2], 8: True because 3 + 5 = 8 
[1, 3, 5, 23, 2], 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