Re: [algogeeks] Re: doubt in spoj 8473 ways
@anubhav i too didn't find it on google bt may be it is: f(n)= ((4n-2)/n)*f(n-1)n1 2 n=1 On Fri, Dec 16, 2011 at 8:07 AM, anubhav raj anubhaw@gmail.com wrote: @samm:i hv googled it several time bt by code no path r ways as a tag bt cudnt get ne link..cn u plz paste the link here.i jst want 2 do ittnx in advnce -- 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.
[algogeeks] Any book suggestion for Data structure and 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: doubt in spoj 8473 ways
@all got AC 114 still i think without some other way to input/output it hard to get below 100. can some1 suggest some better (smaller ) way to i/o integers On Sat, Dec 17, 2011 at 1:31 AM, sourabh singh singhsourab...@gmail.comwrote: @anubhav i too didn't find it on google bt may be it is: f(n)= ((4n-2)/n)*f(n-1)n1 2 n=1 On Fri, Dec 16, 2011 at 8:07 AM, anubhav raj anubhaw@gmail.comwrote: @samm:i hv googled it several time bt by code no path r ways as a tag bt cudnt get ne link..cn u plz paste the link here.i jst want 2 do ittnx in advnce -- 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] Any book suggestion for Data structure and algo.
Google this 6.046 You should not ask any more suggestion till you complete the above On Sat, Dec 17, 2011 at 3:07 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: -- 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] Any book suggestion for Data structure and algo.
Cool Rahul On Sat, Dec 17, 2011 at 3:09 PM, Rahul raikra...@gmail.com wrote: Google this 6.046 You should not ask any more suggestion till you complete the above On Sat, Dec 17, 2011 at 3:07 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: -- 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. -- 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] Any book suggestion for Data structure and algo.
If you have time then Do a Google this www.algo-class.org On Sat, Dec 17, 2011 at 3:13 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: Cool Rahul On Sat, Dec 17, 2011 at 3:09 PM, Rahul raikra...@gmail.com wrote: Google this 6.046 You should not ask any more suggestion till you complete the above On Sat, Dec 17, 2011 at 3:07 PM, Abhishek Goswami zeal.gosw...@gmail.com wrote: -- 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. -- 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] Any book suggestion for Data structure and algo.
ya Sure Thx bro On Sat, Dec 17, 2011 at 3:15 PM, Rahul raikra...@gmail.com wrote: If you have time then Do a Google this www.algo-class.org On Sat, Dec 17, 2011 at 3:13 PM, Abhishek Goswami zeal.gosw...@gmail.comwrote: Cool Rahul On Sat, Dec 17, 2011 at 3:09 PM, Rahul raikra...@gmail.com wrote: Google this 6.046 You should not ask any more suggestion till you complete the above On Sat, Dec 17, 2011 at 3:07 PM, Abhishek Goswami zeal.gosw...@gmail.com wrote: -- 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. -- 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. -- 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] doubt on normalization coding
hai friends this is ramesh . i need c or cpp code for normalisation ,how the normlaiztion will be performed on a realtion up to third normal formplease... if any one knows about it please send that code ..please please... -- 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] doubt on normalization coding
No homework post please. On Sat, Dec 17, 2011 at 6:26 PM, rameshbabu kovuru rameshbabukv...@gmail.com wrote: hai friends this is ramesh . i need c or cpp code for normalisation ,how the normlaiztion will be performed on a realtion up to third normal formplease... if any one knows about it please send that code ..please please... -- 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: doubt in TSUM
Hi,
*TSUM:*
This is also a brute-force approach..
Pls correct me if i m wrong
Algorithm:
1.sort the array
2.find the sum of the three min elements - sum_min
3.find the sum of the three max elements - sum_max
4.for each value in [sum_min,sum_max]
binary search for the triplet
int count=0;
Arrays.sort(a);
int sum_min=a[0]+a[1]+a[2];
int sum_max=a[a.length-1]+a[a.length-2]+a[a.length-3];
for(int sum=sum_min;sum=sum_max;sum++)
{
for(int i=0;ia.length;i++)
{
for(int j=i+1;ja.length;j++)
{
if(Arrays.binarySearch(a,sum-a[i]-a[j]) j)
{
count++;
}
}
}
System.out.println(sum+:+count);
count=0;
}
--
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: Suggest Algo for this Question
@Lucifer : if for the same question , we consider a Max heap instead of Min heap then complexity of the same algo will be O(N) ... right??? On Fri, Dec 16, 2011 at 8:50 PM, Lucifer sourabhd2...@gmail.com wrote: @my previous post.. While explaining the run-time I have made an editing mistake... instead of 'N' nodes it should be 'K' nodes.. i.e. Hence, for any given bin- tree having 'K' nodes, the number of null nodes is 'K+1'. These null nodes are nothing but the nodes where the check nodeValue X failed while traversing the original tree. Hence, the total number of checks will be 2K+1 = O(2K) On Dec 16, 1:04 am, sunny agrawal sunny816.i...@gmail.com wrote: oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the child nodes have value X or one of them or node, at the end we always end up making 2 checks for the children (left and right child). So given any tree one can think of a null node as a leaf node ( depicting that the node has a value =X) . Hence, for any given bin- tree having nodes 'N', the number null nodes is 'N+1'. Hence, the total number of checks will be 2N+1 = O(2N) , On Dec 15, 1:00 pm, WgpShashank shashank7andr...@gmail.com wrote: @sunny why we look at all k number which are greater then x , correct ? Lets think in this way we wants to check if kth smallest element in heap thats =x isn't it ? so if root of mean heap is greater then x then none other elements will less then x so we terminate . else our algorithm will search children of all the nodes which are less then x till either we have found k of them or we are exhausted e.g. when k=0 . so we will cal our function to both left right children ? so now think we are looking for children's of only nodes which are less then x and at most k of these in tottal . each have
Re: [algogeeks] zig zag problem
please see the algo and let me know if i am doing it wrong:-
toggle= arr[i+1] arr[i];
subseq=0;
for( i=0 ; ilen ;i++)
{
if ( toggle == 1)
{
if( arr[i+1] arr[i])
{
subseq=subseq+2;
}
toggle=0;
}
else
{
if(arr[i] arr[i+1])
{
subseq=subseq+2;
}
toggle=1;
}
}
print subseq;
On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta sangeeta15...@gmail.com wrote:
Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences
between successive numbers strictly alternate between positive and
negative. The first difference (if one exists) may be either positive
or negative. A sequence with fewer than two elements is trivially a
zig-zag sequence.
For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences
(6,-3,5,-7,3) are alternately positive and negative. In contrast,
1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because
its first two differences are positive and the second because its last
difference is zero.
Given a sequence of integers, sequence, return the length of the
longest subsequence of sequence that is a zig-zag sequence. A
subsequence is obtained by deleting some number of elements (possibly
zero) from the original sequence, leaving the remaining elements in
their original order
--
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.
[algogeeks] Re: doubt in TSUM
You will not be able to get the correct solution with this algo becoz
ur algo will not able to generate all the 3 triplets sum.
You hav to loop through all the triplets ...
take for example the numbers :-
1 2 3 5 6..
Ur algo will generate the following triplet sum as
9 10 12 8 6 11 13 10 14 ... The mistake is that one more triplet sum
9 is missing . [ Triplet possible = { 5c3 = 10 } != 9 ]
--
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: doubt in spoj 8473 ways
@saurav: if you dnt mind cn i c ur code...like earlier your post was also related to f(n) bt it wz out f d limit -- 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] suggest algo
suggest algo to find k most frequently occuring numbers from a file of very large size containing numbers. -- 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: doubt in TSUM
@All , The problm can be solved by Fast Fourier Transform . The Concept used here is to Convert the number in the array into a vector and Then apply multiplication using FFT . The below example will clear it . I will start will finding Pair of all Number equal to every possible combination from a given set of numbers:- Take for example : Array Element :- 1 , 2 , 3 , 5 , 6 -- Combination Possible are :- Pair Sum No of times 3 1 4 1 6 1 7 2 5 1 8 2 9 1 11 1 12 1 Represent it in the form of a polynomial to get - f(x) = x + x^2 + x^3 + x^5 + x^6 Now calculate G(x)=f(x)*f(x) , rendering us the Polynomial as :- G(x) = x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 4x^7 + 4x^8 + 2x^9 +2x^11 + x^10 + x^12 The number of the form in the above polynomial : = [A* X^N] --- (int)(A/2) Give the number repeatation for the Pair Sum N . For example :- The Pair Sum 3 is the repeated floor(3/2) =1 times :- The Pair Sum 7 8 is the repeated floor(4/2) =2 times Similarly For getting the Value of Triplet Sum we need need to do multiplication on some polynomials (Done by FFT) . I liked this problm very much , it cost me much time , but I came to know abt the importance of FFT in Digital signalling . -- 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: doubt in spoj 8473 ways
@anubhav No,i can't post an AC code here . takes all fun out of spoj problem solving thing. i can just hint that i used the function posted earlier and u don't need to make a function single for loop will do. that's it try harder. buddy :-) btw it got ac 111 later :-). On Sat, Dec 17, 2011 at 5:43 AM, anubhav raj anubhaw@gmail.com wrote: @saurav: if you dnt mind cn i c ur code...like earlier your post was also related to f(n) bt it wz out f d limit -- 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.
[algogeeks] Re: Suggest Algo for this Question
@atul.. Complexity would be 2(n-k+1) = O(2*(n-k)) Basically the condition based on which the traversal is performed will change. I have modified some part of the original post to show that: Instead of having the initial count as K have it as N-K+1 .. when taking a max-heap.. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is X then skip the processing of the tree rooted at the current node. 2) If current node is = X , then decrement the initial count i.e (n-k +1) by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of initial count 0 then the kth smallest element is X. b) If during tree traversal the value of initial count reaches 0, that means there are atleast (n-k+1) elements which are = X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element = X. On Dec 17, 1:28 pm, atul anand atul.87fri...@gmail.com wrote: @Lucifer : if for the same question , we consider a Max heap instead of Min heap then complexity of the same algo will be O(N) ... right??? On Fri, Dec 16, 2011 at 8:50 PM, Lucifer sourabhd2...@gmail.com wrote: @my previous post.. While explaining the run-time I have made an editing mistake... instead of 'N' nodes it should be 'K' nodes.. i.e. Hence, for any given bin- tree having 'K' nodes, the number of null nodes is 'K+1'. These null nodes are nothing but the nodes where the check nodeValue X failed while traversing the original tree. Hence, the total number of checks will be 2K+1 = O(2K) On Dec 16, 1:04 am, sunny agrawal sunny816.i...@gmail.com wrote: oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier @shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand atul.87fri...@gmail.com wrote: @Lucifer : yes even i found flaw in the above algo when i gave it a second thought but didnt get time to post it. bcoz min heap has property that the parent node is less than its both child(subtree to be more precise ) but it does not confirm that left child is always smaller than right child of the node. On Thu, Dec 15, 2011 at 10:31 PM, Lucifer sourabhd2...@gmail.com wrote: @All I don't think the algo given above is entirely correct.. Or may be i didn't it properly... So basically say a preorder traversal of the heap is done based on whether the current root value X. As the algo says that at any point if k0 and we hit a node value which is =X , then we are done. If i understood it properly then thats not correct. The reason being that say on the left subtree we end up at a node whose value is =x and say k 0. Now until and unless we don't parse the right subtree (or basically the right half which was neglected as part of pre-order traversal or say was to be considered later) we are not sure if the current node is actually withing the first smallest K nos. It may happen that previously neglected (or rather later to be processed) half has the kth smallest element which is actually X. The reason being that a heap is not a binary search tree where there is a strict relation between the left and the right half so that we can say that if say a condition P is true in the left half then it will be false in the right half and vice versa. To solve the problem we need to do a pre-order traversal keeping the following conditions in mind: (pass K and root node) 1) If current node is = X then skip the processing of the tree rooted at the current node. 2) If current node is X , then decrement K by 1 and process its childs ( i.e take step 1 for rach child). The result will depend on: a) If at any stage recursion ends and the value of K0 then the kth smallest element is = X. b) If during tree traversal the value of K reaches 0, that means there are atleast k elements which are X. Hence, at this point terminate the recursion ( as in no need to continue). This result signifies that the kth smallest element X. Therefore to generalize... Perform a preorder traversal for root node X, and keep decrementing the count K by 1. If K reaches 0 during traversal then end the recursion. After the call to the recursive traversal is over, check for the value of K. If greater than 0, then the kth smallest element = X otherwise its not. The time complexity will always be 2K ( in the worst case basically when K value reaches 0 ). If u analyze it closely we are making 2 checks when at particular node for its children. Hence, whether both the
[algogeeks] A new app!!
My friend has developed an iphone gaming app and has launched it on app store .Here are the links to the app intro and sample video of that.Have a glimpse of that.. With regards, Naveen M S This is itunes download link http://itunes.apple.com/us/app/naughty-eggs/id486789170?ls=1mt=8 Follow on Twitter http://twitter.com/Naughtyeggs Facebook Fan page (click like on this page) http://www.facebook.com/pages/Naughty-Eggs/193722604052649?sk=app_208195102528120 Demo Video (embed in your facebook wall) http://www.youtube.com/watch?v=J69Z-HEiLes -- 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: doubt in TSUM
@SAMMM Hi Nice Solution.How did u relate it to FFT ? On Sat, Dec 17, 2011 at 9:56 PM, SAMMM somnath.nit...@gmail.com wrote: @All , The problm can be solved by Fast Fourier Transform . The Concept used here is to Convert the number in the array into a vector and Then apply multiplication using FFT . The below example will clear it . I will start will finding Pair of all Number equal to every possible combination from a given set of numbers:- Take for example : Array Element :- 1 , 2 , 3 , 5 , 6 -- Combination Possible are :- Pair Sum No of times 3 1 4 1 6 1 7 2 5 1 8 2 9 1 11 1 12 1 Represent it in the form of a polynomial to get - f(x) = x + x^2 + x^3 + x^5 + x^6 Now calculate G(x)=f(x)*f(x) , rendering us the Polynomial as :- G(x) = x^2 + 2x^3 + 3x^4 + 2x^5 + 3x^6 + 4x^7 + 4x^8 + 2x^9 +2x^11 + x^10 + x^12 The number of the form in the above polynomial : = [A* X^N] --- (int)(A/2) Give the number repeatation for the Pair Sum N . For example :- The Pair Sum 3 is the repeated floor(3/2) =1 times :- The Pair Sum 7 8 is the repeated floor(4/2) =2 times Similarly For getting the Value of Triplet Sum we need need to do multiplication on some polynomials (Done by FFT) . I liked this problm very much , it cost me much time , but I came to know abt the importance of FFT in Digital signalling . -- 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.
