@atul..
Why both 'l--' and 'm--' together ? doing this you will miss out on
lot of intermediate values..
Also, if the array sorted and u want to capture the all valid values
for check in the minimum runtime then instead of having 2 right
pointers, have 1 left and 1 right pointer and inc/dec one
@atul..
Yes,
j=K and p=4
Also would like to mention that in my first post I have mentioned
about a variable 'R' and not used it in the explanation..
Actually 'R' is nothing but 'p', in case you got confused...
On Jan 2, 8:20 am, Arun Vishwanathan wrote:
> does this make sense?
> 1)sort arra
@atul...
The only reason behind storing the indices instead of actual element
values in the heap, as mentioned in my original post, was to resolve
the issues that u have brought up...
Cheers :)
On Jan 2, 11:08 am, Lucifer wrote:
> @atul..
>
> There are no stability or access issues with the cod
@atul..
There are no stability or access issues with the code..
Below i have given explanation for ur concerns...
--
a) I think ur first concern is a stable heap...
The heap might not be stable as u have mentioned.. but the code makes
it stable..
Hence, it won'
if i am getting it right then i guess because heap is not stable i.e it
does not guarantee that if there is multiple same elements say 4,4,4,5,5,10
then doing extract min and extract max would may not give oldest index or
you can say that 1st occurance of those multiple same elements i.e
arr[]=
does this make sense?
1)sort array O(nlogn)
2)keep 4 pointer to last 4 elements of array. At each point in the
algorithm we need to ensure than i wrote:
> sort(arr);
> min=arr[0]+arr[1]+arr[2]+arr[3];
> max=arr[n-1]+arr[n-2]+arr[n-3]+arr[n-4];
>
> for(i=0;i {
> a=arr[i];
> k=i+1;
> l=n-1;
> m
sort(arr);
min=arr[0]+arr[1]+arr[2]+arr[3];
max=arr[n-1]+arr[n-2]+arr[n-3]+arr[n-4];
for(i=0;i num)
{
l--;
m--;
}
else
{
k++;
}
}
if(flag)
break;
}
complexity = O(N^2);
--
You received this message because you are subscribed to
if you want to find all combination of number which will sum to K
then change block if(a+b+c+d == num) and remove flag and break to :-
if(a+b+c+d == num)
{
printf("\nNumber found (%d + %d + %d + %d ) = %d",a,b,c,d,num);
k++;
l--;
m--;
}
--
You received this message because you are subscribed
@Lucifier :
for the else case;
suppose arr is 6,10,8,5,9,7,1,5,4,3K=8
at max =10 , min =1 condition will fail
A[j] = A[Top(minH)];
currentStrInd = Top(MaxH) +1; // currentStrInd = index of 8
pop(Top(MaxH));
now because of A[Top(MaxH)] - A[Top(MinH)] <= K (9 -1= 8)condition in while
loop
@Lucifier :
X( A[i, j], p ) = X( A[i - 1, j], p ) || X( A[i - 1, j - A[i]] , p- 1) ;
here j = K and p=4 // as mentioned in the question??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@goo
Shady ,
how do you valide the case that a, b, c, d are diferente, i.e a=x[i] ,
b=x[j], i!=j ?
2012/1/1 Lucifer
> @ SAMM..
>
> The following might work, but would need verification..
>
> Below solution is for a generic no. of elements.
> In your case its 4.
> Lets represent 4 by R.
>
> Lets take
@ SAMM..
The following might work, but would need verification..
Below solution is for a generic no. of elements.
In your case its 4.
Lets represent 4 by R.
Lets take a 2-dim array named A, to store the intermediate values..
Now, X ( A[i, j] , p ) basically means whether given the first 'i'
ele
@atul..
Below i have explained how the reduction from N^2 to N log N approach
will work..
Space complexity 2*N = O(N)
The following data structures will be used to optimize the same :-
1) a min-heap named MinH - say X[N] can be used to implement the min-
heap.
2) a max- heap named MaxH - say Y[
O((n^2)*logn)
if problem is a+b+c+d=e
find all combinations of e-a-b O(N^2) as e is constant
similarly find for c+d also O(N^2)
then sort then so O((N^2)*logn)
and do a binary search for each value of e-a-b in c+d array
On Sun, Jan 1, 2012 at 11:08 PM, SAMMM wrote:
> HAPPY NEW YEAR to al
HAPPY NEW YEAR to all Geeks !!!
Given an array of size N and a integer Num(K) . Need to find the
combination of four no's in the array whose sum is equal to Num(K).
Needed a solution whose complexity is less than O(n^3) .
--
You received this message because you are subscribed to the Google Gr
Given an array A[] and a integer num(K) . Need to find the combination
of four no's in the array whose sum is equal to num(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
Lucifier : i didnt read your second approach ..but yeah i have implemented
the same.
nice :)
did u come up with NlogN approach??
--
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.
one of the reason why we set all messages to moderation.
Happy new year.
On Sun, Jan 1, 2012 at 7:27 PM, geek forgeek wrote:
> anyone ?
>
> On Sun, Jan 1, 2012 at 4:05 PM, geek forgeek wrote:
>
>> Hello Everyone ,
>> I have finished all the standard algorithms in the one - semester
>> curriculu
anyone ?
On Sun, Jan 1, 2012 at 4:05 PM, geek forgeek wrote:
> Hello Everyone ,
> I have finished all the standard algorithms in the one - semester
> curriculum of the B-Tech course.
> I want help on the kind of algorithms i should do now .
>
> I get difficulty in doing problems in competitions
@atul
Is the above code's optimization based on the 2nd approach that i have
mentioned above or is it something different..
In case, you are doing something else can u provide us with more
explanation so that it would be easier for everyone to understand the
code ...
On Jan 1, 3:55 pm, atul ana
ok ...
@Lucifier i have optimized your code further so that there is no need to
check every element i.e to outer for loop..
so i have skipped elements if they can never be part of second maxLen
sequence if exits.
int find_seq(int arr[],int *start,int *end,int k,int n)
{
int maxLen=0;
int min=arr[0
@Ashish
We can sort a list in another way as follows:
1) Recursively divide the list into two halves..
2) Call merge while joining the sorted lists..
MergeSort(node * p)
{
if ( p contains only one element)
return p;
p1 = MergeSort(first half of list pointed by p);
Hello Everyone ,
I have finished all the standard algorithms in the one - semester
curriculum of the B-Tech course.
I want help on the kind of algorithms i should do now .
I get difficulty in doing problems in competitions like on topcoder ,
codechef etc.So Kindly suggest links or books for the sa
23 matches
Mail list logo
