Hi,
I can think of an approach that is neither recursion nor dynamic
programming. ( I would like to know, how to solve it using dp, as you say,
though)
1. Take an auxiliary array SUM which stores the sum of all entries from
beginning to that index.
2. Now, you have to find all the pairs(i,j | j > i, SUM[j] - SUM[i] == k)
3. Start from right, use a C++ STL map or Java TreeMap to store (number
minus k) and its ocurence count and add the occurence count to the answer.
I will explain for the given example.
arr = [1,3,1,7,-4,-11,3,4,8]
SUM = [0,1,4,5,12,8,-3,0,4,12] (We always start from second index in
the SUM array storing 0 for the first index)
map<int,int> M;
answer = 0;
iterating from right,
12 -> answer = answer + M[12] (=0), M[ 12 - 12 ] = 1
4 -> answer = answer + M[4] (=0), M [ 4 - 12] = 1
0 -> answer = 0 + M[0] , M [-12] = 1
notice, how the answer will now be 1. Why, you ask, because I found a pair
of indices which was required.
-3 -> answer = 1 + M[-3], M [-15] = 1
8 -> answer = 1 + M[8], M [-4] = 1
12 -> answer = 1 + M[12], M[0] = 2
because M[0] was 1 before.
5 -> answer = 1 + M[5], M[-7] = 1
4 -> answer = 1 + M[4], M[-8] = 2
1 -> answer = 1 + M[1], M[-11] = 1
0 -> answer = 1 + M[0], M[-12] = 2
hence,
answer = 3.
Insertion in map takes logarithmic time. Overall complexity will be
O(nlog(n))
NOTE:
If you have to output indices, rather than the number, you can use a
map<int, vector<int>> in which case the vector will store all the indices,
where the number came, and its size will tell the count.
I hope that makes sense. Feel free to ask if you didn't get something.
On Sun, Feb 21, 2016 at 3:18 PM, Shubh Aggarwal <shubh.aggarwal...@gmail.com
> wrote:
> Given an array of n elements(both +ve -ve allowed)
> Find all the subarrays with a given sum k!
> I know the solution using dynamic programming. It has to be done by
> recursion (as asked by the interviewer)
>
> For ex
>
> arr = 1 3 1 7 -4 -11 3 4 8
>
> k = 12
>
> answer = {1 3 1 7}, {4 8}, {1 3 1 7 -4 -11 3 4 8}
>
> You have to print {from index, to last index} so for above example {0,
> 3}; {0,8}; {7,8} is the answer
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
- Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
