CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Count of sub-arrays with a given sum such that the indices are in ascending order

  1. #1
    Join Date
    Jan 2020
    Posts
    5

    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.

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,576

    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?

  3. #3
    Join Date
    Feb 2017
    Posts
    528

    Re: Count of sub-arrays with a given sum such that the indices are in ascending order

    Quote Originally Posted by gamerrk1004 View Post
    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.

  4. #4
    Join Date
    Jan 2020
    Posts
    5

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)