Given an array and a number , how do I find that sum of any consecutive array elements equals the given number ?

[Mahesh Mesta]

Hi all,

Given an array and a number , how do I find that sum of  any consecutive array elements equals the number. Example
Given array [1, 3, 4, 5, 2] and the given number is 12, since here the consecutive numbers 3 + 4 + 5 = 12  hence it should return true. I am trying to wrap my head around it, but couldn't find the solution, please help !

Regards,
Mahesh

[Aboobacker MK]

You can try the following brute forcing method if the given array is very small

a =[1,3,4,5,2]
(1..a.length).each do |num|
  a.each_cons(num).each do |pair|
    return true if  pair.inject(:+) == 12
  end
end
return false

Otherwise try methods like this
http://www.geeksforgeeks.org/find-subarray-with-given-sum/

Regards
Aboobacker

--
You received this message because you are subscribed to the Google Groups "BANGALORE RUG-Ruby Users Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bangalorerug...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Amit Mathur]

On Wed, Jun 29, 2016 at 7:18 PM, Aboobacker MK <abooba...@gmail.com> wrote:

You can try the following brute forcing method if the given array is very small

a =[1,3,4,5,2]
(1..a.length).each do |num|
  a.each_cons(num).each do |pair|
    return true if  pair.inject(:+) == 12
  end
end
return false

It looks like there is no better way than 2 nested loops and hence n^2 complexity. But if your array is small (say, size less than 30) , speed should not be a problem.

You can also try couple of small optimizations:

a) if the running sum in the inner loop already exceeds the required sum, break out of the inner loop

b) if the sum starting from any index to the end of the array is less than the required sum, then the required sum is unattainable. So, end the program

def find_sequence_with_sum(a, t)

  first_to_last_sum = 0

  (0..a.size-1).each do |first|

    (first..a.size-1).each do |last|

      # use sum instead of inject in line below if using Rails

      first_to_last_sum = a[first..last].inject(0, :+)

      return [first, last] if first_to_last_sum == t

      break if first_to_last_sum > t

    end

    break if first_to_last_sum < t

  end

  return nil

end

# test code below

def find_and_print_sequence_with_sum(a, t)

  first, last = find_sequence_with_sum(a, t)

  if !first.nil? && !last.nil?

    puts "#{t} in #{a} -> #{a[first..last]}"

  else

    puts "#{t} in #{a} -> None"

  end

end

(0..20).each do |total|

  puts find_and_print_sequence_with_sum([1, 3, 4, 5, 2], total)

end

[Chetan Agrawal]

The best solution here would be n.log(n) and would follow the dynamic programming.

You would sort of reuse the already calculate sum and not recalculate them again.

// pseudo  code

var dp[n][n]

for i in 1 to n

  for j in 0 to n-i

    if i != j

      dp[i][j] = dp[i-1][j] + arr[i][j]

      if dp[i][j] == sum return true

return false

--

Best,

Chetan Agrawal

Mob: +91.74830.53630

How I Seek Meaning & Transform Lives: I believe Existence is in the form of Co-Existence. Every individual, every matter, every unit exists to co-exist with everything else, to form a bigger & better unit, a developed entity. I want to reach the ultimatum of my existence, and pull with me everyone else for the common goal.

[Amit Mathur]

On Wed, Jun 29, 2016 at 11:24 PM, Chetan Agrawal <cheta...@gmail.com> wrote:

The best solution here would be n.log(n) and would follow the dynamic programming.

You would sort of reuse the already calculate sum and not recalculate them again.

Dynamic programming idea is excellent!

However, I think we got the complexities wrong. Counting the sum operations, the earlier iterative solutions are O(n^3) and the dynamic programming solution is O(n^2).

[Chetan Agrawal]

It appears to be n^2 because of 1 nested loop.
But eventually it will be n.log(n).

The nested loop goes from 0 to n-i, where i is increasing at each step.

--

Best,

Chetan Agrawal

Mob: +91.74830.53630

How I Seek Meaning & Transform Lives: I believe Existence is in the form of Co-Existence. Every individual, every matter, every unit exists to co-exist with everything else, to form a bigger & better unit, a developed entity. I want to reach the ultimatum of my existence, and pull with me everyone else for the common goal.

[Amit Mathur]

On Sat, Jul 2, 2016 at 3:32 PM, Chetan Agrawal <cheta...@gmail.com> wrote:

It appears to be n^2 because of 1 nested loop.
But eventually it will be n.log(n).

The nested loop goes from 0 to n-i, where i is increasing at each step.

The outer loop i.e. i goes from 1 to n, where as the inner loop i.e. j goes from 0 to n-i.

when i=1, j runs through 0, 1, 2, ... n-1

when i=2, j runs through 0, 1, 2, ... n-2

and so on..

when i=n-1, j runs through 0, 1

when i=n, j runs through only 0

So, if you sum up number of iterations starting from the last to first, it is 1+2+3+...+n = (n+1) * n / 2 = O(n^2).

[Chetan Agrawal]

Ah. Yes. You are right. My bad.
I was thinking exponential summation in my head.

Sorry to confuse.

--

Best,

Chetan Agrawal

Mob: +91.74830.53630

How I Seek Meaning & Transform Lives: I believe Existence is in the form of Co-Existence. Every individual, every matter, every unit exists to co-exist with everything else, to form a bigger & better unit, a developed entity. I want to reach the ultimatum of my existence, and pull with me everyone else for the common goal.

--

[Surya]

Can be done in O(n):

a = [1, 3, 4, 5, 2]

sum = 12

hash_map = Object.new

hash_map.instance_eval do

  class << self

    attr_accessor :head, :tail

  end

end

hash_map.head = hash_map.tail = 0

check_sum = a[hash_map.head]

found = true

1.upto(a.count - 1) do |i|

  found = if (check_sum == sum)

    found = true

    break

  else

    found = false

  end

  check_sum = check_sum + a[i]

  hash_map.tail = i

  if (check_sum > sum)

    check_sum = check_sum - a[hash_map.head]

    hash_map.head = hash_map.head + 1

  end

end

if found

  puts "subarray is: #{a[hash_map.head..hash_map.tail]}"

else

  puts "no subarray for sum: #{sum}"

end

Basically, you take three temp variables check_sum, head, and tail, keep head set to 0 and tail to 1, keep moving tail with the loop and keep adding value of that index from tail to check_sum. If check_sum matches your sum then update our found flag and break the loop, otherwise keep adding index value to it. If check_sum is greater than the sum value that we seek then subtract the index value of array from head and increase the head value by one. So, we do this whole calculation in just one iteration. So, O(n).

--

You received this message because you are subscribed to the Google Groups "BANGALORE RUG-Ruby Users Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bangalorerug...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Please consider the environment before printing this email.

Regards,
Surya

[Surya]

Sorry, the correct code is:

a = [1, 3, 4, 5, 2]

sum = 12

hash_map = Object.new

hash_map.instance_eval do

  class << self

    attr_accessor :head, :tail

  end

end

hash_map.head = hash_map.tail = 0

check_sum = a[hash_map.head]

found = true

1.upto(a.count - 1) do |i|

  if (check_sum == sum)

    found = true

    break

  else

    found = false

  end

  check_sum = check_sum + a[i]

  hash_map.tail = i

  if (check_sum > sum)

    check_sum = check_sum - a[hash_map.head]

    hash_map.head = hash_map.head + 1

  end

end

if found

  puts "subarray is: #{a[hash_map.head..hash_map.tail]}"

else

  puts "no subarray for sum: #{sum}"

end

[Hemant Kumar]

Surya,

Cool idea, but it does not work. For example, try running your code with sum=14. The problem is, you are only dropping from end of array - if check_sum > sum, which works in some cases but not always.  There isn't a solution faster than nlg(n) possible for this particular problem.

Cheers

Hemant

Co founder - http://www.codemancers.com

http://twitter.com/gnufied

[Chetan Agrawal]

nlog(n) might be possible using segment trees. As it also talks about a range.
Havent thought of the algorithm to break the items, though.

Any other approaches for nlog(n).

--

Best,

Chetan Agrawal

Mob: +91.74830.53630

How I Seek Meaning & Transform Lives: I believe Existence is in the form of Co-Existence. Every individual, every matter, every unit exists to co-exist with everything else, to form a bigger & better unit, a developed entity. I want to reach the ultimatum of my existence, and pull with me everyone else for the common goal.

[Santosh T]

Hi,

Just trying out this approach. Check if this works for you.

a = [1,3,4,5,2]

arr = 1.upto(5).flat_map{|n| a.combination(n).to_a}

arr.keep_if{|ar| ar.inject(0){|sum, i| sum + i} == 12 }

ar_sum = arr.keep_if{|ar| ar.inject(0){|sum, i| sum + i} == 12 }

return true unless ar_sum.blank? 

Regards,

Santosh T

Regards,
Santosh T.

[Hemant Kumar]

Well here is nlg(n) https://gist.github.com/gnufied/dcf24c34f02ac5f058637af6b614b799 version using divide & conquer. 

[Surya]

Hemant,

Got it, my bad that I missed this corner case. You're right, it would be done in O(n logn):

a = [1, 3, 4, 5, 2]

sum = 14

head = tail = 0

check_sum = a[head]

found = true

while tail < a.count

  while check_sum > sum && head < tail

    check_sum = check_sum - a[head]

    head = head + 1

  end

  if (check_sum == sum)

    found = true

    break

  else

    found = false

  end

  tail = tail + 1

  check_sum = check_sum + a[tail] if a[tail]

end

if found

  puts "subarray is: #{a[head..tail]}"

else

  puts "no subarray for sum: #{sum}"

end

#=> subarray is: [3, 4, 5, 2]

On 3 July 2016 at 03:04, Hemant Kumar <hem...@codemancers.com> wrote:

[Anand Chitipothu]

I'm surprised why no one has tried a recursive solution. Here is my attempt.

# https://gist.github.com/anandology/990ec7b9b52526d7122606644c3dd4ec

def search(array, sum, expected, head, tail)

    if head > tail

        return false

    elsif sum == expected

        return [head, tail]

    else

        return (search(array, sum - array[head], expected, head+1, tail) or search(array, sum - array[tail], expected, head, tail-1))

    end

end

def search_sum(array, expected)

    sum = array.inject(0){|sum,x| sum + x }

    result = search(array, sum, expected, 0, array.length-1)

    if result

        head_, tail = result

        return array[head_..tail]

    end

end

    

print(search_sum([1, 3, 4, 5, 2], 12))

print("\n")

This is not optimal, there is still room for improvement.

Anand

[viresh s]

Please pardon me for using short variable names. I could do it in o(n)

a = [1, 3, 4, 5, 2]

s = 14

sum_to_i = {}

sum = 0

a.each {|i| sum += i; sum_to_i[sum] = i}

puts sum_to_i.inspect

sum_to_i.keys.each {|i|

  if sum_to_i[i - s]

    print "found"

    exit 0

  end

}

print "not found"

VireshAS

[Anand Chitipothu]

On Mon, 4 Jul 2016 at 08:27 viresh s <asvi...@gmail.com> wrote:

Please pardon me for using short variable names. I could do it in o(n)

a = [1, 3, 4, 5, 2]

s = 14

sum_to_i = {}

sum = 0

a.each {|i| sum += i; sum_to_i[sum] = i}

puts sum_to_i.inspect

sum_to_i.keys.each {|i|

  if sum_to_i[i - s]

    print "found"

    exit 0

  end

}

print "not found"

Clever!

One issue though. It just prints whether or not a solution is found. Some more tweaks are required to print the actual result. You need to store the index as value in the hash, not the element of the array.

Anand 

 

[viresh s]

@anand done.

a = [1, 3, 4, 5, 2]

s = 14

sum_to_i = {}

sum = 0

a.each_with_index {|i, j| sum += i; sum_to_i[sum] = j}

sum_to_i.keys.each_with_index {|i, j|

  val = sum_to_i[i - s]

  if val

    puts "found: #{a[(val + 1)..j]}" if val

    exit 0

  end

}

puts "not found"

--

You received this message because you are subscribed to the Google Groups "BANGALORE RUG-Ruby Users Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bangalorerug...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

VireshAS

[Amit Mathur]

Try,

a = [1, 3, 4, 5, 2]

s = 8

it think it does not work.

[Anand Chitipothu]

On Mon, 4 Jul 2016 at 13:21 Amit Mathur <a.k.m...@gmail.com> wrote:

Try,

a = [1, 3, 4, 5, 2]

s = 8

it think it does not work.

That seems to be a bug. Initiazing sum_to_i as below seems to be fixing it.

sum_to_i = {0 => 0}

Anand

[Amit Mathur]

Try s = 13 or 15. Doesn't seem to work.

--

[viresh s]

Hi Amit,

@amit thank you trying it out.

@anand thanks for that patch.

I have fixed that bug here

a = [1, 3, 4, 5, 2]

s = ARGV[0].to_i

sum_to_i = {0 => 0}

sum = 0

a.each_with_index {|i, j| sum += i; sum_to_i[sum] = j + 1}

sum_to_i.keys.each_with_index {|i, j|

  val = sum_to_i[i - s]

  if val

    puts "found: #{a[val..(j-1)]}" if val

    exit 0

  end

}

puts "not found"

##usage

#ruby file.rb 8

--

VireshAS

[Amit Mathur]

Hi Viresh,

You idea is very neat. Although it won't work for 0 or negative numbers, it works well for positive integers. You can test it more thoroughly by converting your code to a method and calling the method repeatedly over a range of values for a and s.

Also, instead of "if val" you can write "if sum_to_i.key?(i-s)" which is closer to your intention I think. Also, if I may suggest, name variables meaningfully. See this quote.

Cheers,

Amit.

[Swanand Pagnis]

+1, Anand. This is the only solution that works with negative numbers. If I were asked this question in an interview, this is what I would write. 

@OP: To approach this problem, I'd start by writing out sums of consecutive elements, starting at each element, and ending at each element. You can easily represent both these sets this in one table, with the diagonal separating the two sets.

Your example: [1, 3, 4, 5, 2]

    1|    4|    8|   13|   15|

    4|    3|    7|   12|   14|

    8|    7|    4|    9|   11|

   13|   12|    9|    5|    7|

   15|   14|   11|    7|    2|

Sorted: [1, 2, 3, 4, 5]

    1|    3|    6|   10|   15|

    3|    2|    5|    9|   14|

    6|    5|    3|    7|   12|

   10|    9|    7|    4|    9|

   15|   14|   12|    9|    5|

Reverse sorted: [5, 4, 3, 2, 1]

    5|    9|   12|   14|   15|

    9|    4|    7|    9|   10|

   12|    7|    3|    5|    6|

   14|    9|    5|    2|    3|

   15|   10|    6|    3|    1|

With negative numbers: [-7, -7, 1, -2, -3, 8]

   -7|  -14|  -13|  -15|  -18|  -10|

  -14|   -7|   -6|   -8|  -11|   -3|

  -13|   -6|    1|   -1|   -4|    4|

  -15|   -8|   -1|   -2|   -5|    3|

  -18|  -11|   -4|   -5|   -3|    5|

  -10|   -3|    4|    3|    5|    8|

So it is quite apparent that this can be brute forced in O(n^2) time, by generating this table. Fairly simple to generate this table.

In the case where there are just positive numbers, there is an immediately apparent pattern of sums being sorted, owing to the fact that sum cannot reduce when numbers are only positive.

When elements are sorted, binary search is your friend. I would start here, and try to come up with a solution.

Hope this helps.

- Swanand

[viresh s]

Hey Amit, thank you for those suggestions. When I attempted this problem, I was just trying to show yet another approach to solve this problem and didnt bother much about code and all the corner-cases. Here is another attempt to solve this problem in O(n).

def find_me_that_sub_array(ar, s)

  sum_to_index_map = {0 => 0}

  running_sum = 0

  ar.each_with_index { |ele, i|

    running_sum += ele;

    sum_to_index_map[running_sum] = i

  }

  sum_to_index_map.keys.each_with_index { |sum, j|

    val = sum_to_index_map[sum + s]

    return ar[j..val] if val

  }

  return nil

end

require 'minitest/autorun'

describe "testing find_me_that_sub_array" do

  it "should work for positive array (1st)" do

    [3,4].must_equal find_me_that_sub_array([1, 2, 3, 4], 7)

  end

  it "should work for positive array (2nd)" do

    [1].must_equal find_me_that_sub_array([1, 2, 3, 4], 1)

  end

  it "should work for positive, negative with 0s array" do

    [1, 2, -3, 0].must_equal find_me_that_sub_array([1, 2, -3, 0, -4, 8], 0)

  end

  it "should work for positive and negative array (1st)" do

    [1, 2].must_equal find_me_that_sub_array([1, 2, -3, -4, 8], 3)

  end

  it "should work for positive and negative array (2nd)" do

    [1, 2, -3].must_equal find_me_that_sub_array([1, 2, -3, -4, 8], 0)

  end

  it "should work for positive and negative array (3rd)" do

    [1, 2, -3, -4].must_equal find_me_that_sub_array([1, 2, -3, -4, 8], -4)

  end

  it "should work for positive and negative array (4th)" do

    [1, 2, -3, -4, 8].must_equal find_me_that_sub_array([1, 2, -3, -4, 8], 4)

  end

  it "should work for positive and negative array (5th)" do

    [-3, -4].must_equal find_me_that_sub_array([1, 2, -3, -4, 8], -7)

  end

end

VireshAS