[algogeeks] Re: subarray wid sum=k
Make an associative sum array ... then find two indexes in the new
array such that b[j] - b[i] =k, which can be done by a hash table. The
found indexes form ur answer , i+1 j.
For e.g
A = {1,2,3,4,5,6,7,8,9}
B = {1,3,6,10,15,21,28,36,45}
and k = 15
now B[5] - B[2] = 15
so ans is 3 5 i.e 4+5+6
Running time O(n).
Regards
Aviral
http://coders-stop.blogspot.com/
On Sep 2, 8:35 pm, Neha Singh neha.ndelhi.1...@gmail.com wrote:
@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;isize;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;isize;i++)
for(int j=0;j=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf(%d %d,i,j); // sub array from index i to j is the
required sub array
}
Time : O(n^2)
Space : O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
bt how to modify it for getting sum value= k? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
the problem can be solved in O(n) time without using extra space .using the algorithm of finding the subarray of maximum sum in a given array.(time complexity is O(n) and no extra space). here you just have to stop when you find sum equal to k. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
here is the solution of O(n) ...
int maxSubArray(int array[],int n) // n is the length of the given array
...
{
int left=0,right=0; // these are to indicate the subscript range on which
we got the max array ..
int temp_left=0;
int max=0,sum=0;
for(int i=0;in;i++)
{
sum += array[i];
if(maxsum)
{
max=sum;
right=i;
left=temp_left;
}
if(sum0) // if the sum is negative ..
{
sum=0;
temp_left=i+1;
}
}
return max;
}
This'll work
On Sun, Sep 4, 2011 at 4:54 AM, tarun kumar taruniit1...@gmail.com wrote:
the problem can be solved in O(n) time without using extra space .using the
algorithm of finding the subarray of maximum sum in a given array.(time
complexity is O(n) and no extra space).
here you just have to stop when you find sum equal to k.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
In my previous post .. if all the array elements are negative .. then it
returns zero and this is also satisfiable ..
On Sun, Sep 4, 2011 at 7:02 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
here is the solution of O(n) ...
int maxSubArray(int array[],int n) // n is the length of the given array
...
{
int left=0,right=0; // these are to indicate the subscript range on which
we got the max array ..
int temp_left=0;
int max=0,sum=0;
for(int i=0;in;i++)
{
sum += array[i];
if(maxsum)
{
max=sum;
right=i;
left=temp_left;
}
if(sum0) // if the sum is negative ..
{
sum=0;
temp_left=i+1;
}
}
return max;
}
This'll work
On Sun, Sep 4, 2011 at 4:54 AM, tarun kumar taruniit1...@gmail.comwrote:
the problem can be solved in O(n) time without using extra space .using
the algorithm of finding the subarray of maximum sum in a given
array.(time complexity is O(n) and no extra space).
here you just have to stop when you find sum equal to k.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: subarray wid sum=k
I Think We can Use HashTable , as Its Sub-Array you are asking about , its obviously contiguous :D Calculate prefix sum , store it in hashtable as key current index as value , once prefix sum=k, print subarray , also keep track of prev index , so that we can print array from prev_i9ndex to current _index where sum=k Time Complexity O(N) Space Complexity O(N) Correct me if anything wrong ? Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xCl1rX3yv5IJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
r u sure space used is O(n)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
The problem in this solution might be the fact that you will get the sub array only if the prefix sum is k... so here we are not using prev index. On Fri, Sep 2, 2011 at 3:17 PM, WgpShashank shashank7andr...@gmail.comwrote: I Think We can Use HashTable , as Its Sub-Array you are asking about , its obviously contiguous :D Calculate prefix sum , store it in hashtable as key current index as value , once prefix sum=k, print subarray , also keep track of prev index , so that we can print array from prev_i9ndex to current _index where sum=k Time Complexity O(N) Space Complexity O(N) Correct me if anything wrong ? Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xCl1rX3yv5IJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
@shasank; i don't think it works... prefix sum means u are taking sum from starting index ... sub array can be from middle ..It is like max sub array in an array problem ...O(n^2) algo is available in Cormen text book .google it . On Fri, Sep 2, 2011 at 6:05 AM, manish kapur manishkapur.n...@gmail.comwrote: r u sure space used is O(n)? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;isize;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;isize;i++)
for(int j=0;j=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf(%d %d,i,j); // sub array from index i to j is the
required sub array
}
Time : O(n^2)
Space : O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
we can do this without taking O(n) space .. but time is O(n^2) as in i
already mentioned where the solution is ...
On Fri, Sep 2, 2011 at 7:35 AM, Neha Singh neha.ndelhi.1...@gmail.comwrote:
@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;isize;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;isize;i++)
for(int j=0;j=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf(%d %d,i,j); // sub array from index i to j is the
required sub array
}
Time : O(n^2)
Space : O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
we have to consider 3 cases ..
1) that sub array can be in first half
2) that sub array can be in second half
3) that sub array can be in middle .
On Fri, Sep 2, 2011 at 7:56 AM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
we can do this without taking O(n) space .. but time is O(n^2) as in i
already mentioned where the solution is ...
On Fri, Sep 2, 2011 at 7:35 AM, Neha Singh neha.ndelhi.1...@gmail.comwrote:
@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;isize;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;isize;i++)
for(int j=0;j=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf(%d %d,i,j); // sub array from index i to j is
the required sub array
}
Time : O(n^2)
Space : O(n)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
@bharatkumar..cn u pls share the algo -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
Logic: since n numbers are there,so there can be (2^n)-1 cases.Just as for n bits we have 2^n possible combinations. Keeping above logic in mind,We can also create a binary tree with root node as 0.From there create 2 child nodes:1)number 2) 0. 1st child node indicates that number was taken in subset and 2nd child node indicates that number was not taken.similarly make a tree with all such possible combinations. FInd sum corresponding to all the the paths. If that sum =k(given) then it means subset exists.Else not. Ashima M.Sc.(Tech)Information Systems 4th year BITS Pilani Rajasthan On Fri, Sep 2, 2011 at 5:26 AM, manish kapur manishkapur.n...@gmail.comwrote: @bharatkumar..cn u pls share the algo -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
@ashima..wat will b the complexity of ur algo? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
@bharat , I never Said that subarray can't start from middle or have to start from 0th index :) Shashank Mani Computer Science Birla Institute of Technology,Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/jUN6eiegbUoJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
Yes Neha, I Never Said That SubArray has to be Started from 0th index,else
What Will be the advantage of this saying subarray anyways, here O(N) time
O(N) space solution
int prefix_sum = 0;
hash_mapint,int find_subarray;
int start_index = -1, end_index = -1;
for (int i = 0,;i n; ++i)
{
if (a[i]==k)
{
start_index = i;
end_index = i;
break;
}
prefix_sum += a[i];
if (prefix_sum==k)
{
start_index = 0;
end_index = i;
break;
}
if (find_subarray.find(prefix_sum) == k)
{
find_subarray[prefix_sum] = i;
}
else
{
start_index = find_subarray[prefix_sum] + 1;
end_index = i;
break;
}
}
if (start_index != -1)
{
cout Zero sum subarray found. Start index : start_index
. End Index: end_index \n;
}
-2 1 -2 5 -1 4 -6 -7 k=9 subarray will be -2 5-1 4 -6
@all Whats Say ?
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/SNpbdnf1PTMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: subarray wid sum=k
ya , it can start from middle ...but continuous right ..
On Fri, Sep 2, 2011 at 4:34 PM, WgpShashank shashank7andr...@gmail.comwrote:
Yes Neha, I Never Said That SubArray has to be Started from 0th index,else
What Will be the advantage of this saying subarray anyways, here O(N) time
O(N) space solution
int prefix_sum = 0;
hash_mapint,int find_subarray;
int start_index = -1, end_index = -1;
for (int i = 0,;i n; ++i)
{
if (a[i]==k)
{
start_index = i;
end_index = i;
break;
}
prefix_sum += a[i];
if (prefix_sum==k)
{
start_index = 0;
end_index = i;
break;
}
if (find_subarray.find(prefix_sum) == k)
{
find_subarray[prefix_sum] = i;
}
else
{
start_index = find_subarray[prefix_sum] + 1;
end_index = i;
break;
}
}
if (start_index != -1)
{
cout Zero sum subarray found. Start index : start_index
. End Index: end_index \n;
}
-2 1 -2 5 -1 4 -6 -7 k=9 subarray will be -2 5-1 4 -6
@all Whats Say ?
Shashank Mani
Computer Science
Birla Institute of Technology,Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/SNpbdnf1PTMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
