-
April 5th, 2020, 09:15 AM
#1
Count of sub-arrays with a given sum such that the indices are in ascending order
Given an array, count the number of sub-arrays 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 sub-arrays, 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 sub-arrays 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 sub-arrays 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 sub-arrays, 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 power-set 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 sub-arrays 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
|