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.c
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 th
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;i wrote:
> the problem can be solved
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 subsc
ya , it can start from middle ...but continuous right ..
On Fri, Sep 2, 2011 at 4:34 PM, WgpShashank wrote:
> 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
>
>
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_map find_subarray;
int start_index = -1, end_index = -1;
for (int i = 0,;i < n; ++i)
{
@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 t
@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.
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 subs
@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
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(
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 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 ca
@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;ihttp://gro
@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 wrote:
>
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 wrote:
> I Think We can Use HashTable , as Its Sub-Array you are asking about , its
> obviously contiguou
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 opti
16 matches
Mail list logo