
April 5th, 2020, 09:15 AM
#1
Count of subarrays with a given sum such that the indices are in ascending order
Given an array, count the number of subarrays with a given sum such that the indices are in ascending order (They do not need to be continuous, but the indices of the elements of the array should be in ascending order.)
For example  Array  {1 2 3 4 5}, Sum  5 Then {1,4} is also a valid sub array as the indices are in ascending order (1 < 4). Others are {2,3} etc.
NOTE  This question seems to be very much similar to the question of count of subarrays, but it becomes more complicated when it comes to the indices being in ascending order as there will be more values then. I request someone to please share a Pseudo Code for the same and if not possible, share the logic.

April 5th, 2020, 01:22 PM
#2
Re: Count of subarrays with a given sum such that the indices are in ascending order
They're array elements, not subarrays. Subarrays have to be contiguous. {2,3} is a subarray, {1,4} is not.
Assume you had to do it with a paper and pencil. What would you do?

April 6th, 2020, 02:02 AM
#3
Re: Count of subarrays with a given sum such that the indices are in ascending order
Originally Posted by gamerrk1004
NOTE  This question seems to be very much similar to the question of count of subarrays, but it becomes more complicated when it comes to the indices being in ascending order as there will be more values then.
A brute force solution is to generate the powerset of the array viewed as a set.
https://en.wikipedia.org/wiki/Power_set
During generation, the subsets with the wanted property are selected.
Last edited by wolle; April 6th, 2020 at 05:42 AM.

April 6th, 2020, 09:47 AM
#4
Re: Count of subarrays with a given sum such that the indices are in ascending order
Thanks for replying everyone. I understood the logic.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
