[algogeeks] Adobe Question
You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111 Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Adobe Question
will an o(n^2) do ? , i have one in mind but will that suffice ? anyways , here it goes make array a[array_length][2]; a[k][0] and a[k][1] will contain the no. of 0's and 1 till kth position. just iterate twice to see where a[i][0]-a[j][0]==a[i][1]-a[j][1] can be maximized . meanwhile i am thinking of other solution . . . . On Tue, Jan 4, 2011 at 2:08 PM, bittu shashank7andr...@gmail.com wrote: You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111 Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Adobe Question
maximum sub sequence whose sum is half of the sub sequence length. On Tue, Jan 4, 2011 at 2:08 PM, bittu shashank7andr...@gmail.com wrote: You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111 Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Puzzle Will Stuck
it's exactly the same question as Buttons on codechef. search this forum , it have been discussed before On Tue, Jan 4, 2011 at 4:13 PM, bittu shashank7andr...@gmail.com wrote: There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles Note 1: Can be done in O(N^2) time and O(1) space. Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Adobe Question
Assuming A[1..n]
i=1,j=n
calculate the initial sum and length of array
let it be s and l
now
if s l/2 then {
.if a[i]=1 then i++
.elseif a[j]=1 then j++
.else i++
}
if s l/2 then {
.if a[i]=0 then i++
.elseif a[j]=0 then j++
.else i++
}
if s=l/2 then it (i,j) is ur answer
i dont know it works for sure or not
but its an O(n)
On Tue, Jan 4, 2011 at 2:08 PM, bittu shashank7andr...@gmail.com wrote:
You have a array of 0's and 1's. e.g.
0001011101001010100101010101100111
Find the maximum contiguous subsequence of the above sequence so the
number of 0's and 1's in that subsequence are equal
Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Aditya Kumar
B-tech 3rd year
Computer Science Engg.
MNNIT, Allahabad.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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] Divide an array into two equal subsets
@vishal may be ur solution is correct but if S very large then its not feasible to have matrix On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Divide an array into two equal subsets
Expecting solution is which is independent of S On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Interview question amazon
Why??? It doesn't help to solve problem. You are already have tree structure with parent links. Taunt. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Divide an array into two equal subsets
How about this algorithm: 1 sort the given array in ascending order 2 traverse from back that is greater to smaller 3 put the 1st read in arrayA and the 2nd read in arrayB 4 put the 3rd read in arrayB and the 4th read in arrayA (notice we have reverse the order of putting the values) 5 repeat the process from step 3 until you have read all the values 6 find sum of the two arrays arrayA and arrayB (notice at this point all values are read and both sets have same no. of elements) 7 find diff of their sums 8 find half value of the diff calculated say that value is 'x' 9 now try to find one no. in both the array with their diff = x such that greater no. is from arrayA and smaller is from arrayB if sum of A sum of B else viceversa. 10 if you don't find any such two no. then the current values in arrayA and arrayB is the solution we are looking for 11 else just replace two no. find in step 9 and repeat the process from step 6 Let me try to explain the algo with these two examples: Example 1: given:1 7 6 4 9 12 sorted : 1 4 6 7 9 12 arrayA: 12 arrayB: arrayA: 12 arrayB: 9 arrayA: 12 arrayB: 9 7 arrayA: 12 6 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 1 at this point all values are read and both sets have same no. of elements now sum of arrayA = 22 now sum of arrayB = 18 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff = 2 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) the two no. are 4 in arrayA and 1 in arrayB replace these two, so now we have: arrayA: 12 6 1 arrayB: 9 7 4 now sum of arrayA = 19 now sum of arrayB = 20 diff of sum = 1 half of diff = 1/2 = 0 (we consider integer values only) Thus the given subsets is the solution: arrayA: 12 6 1 arrayB: 9 7 4 Example 2: given:5 18 3 9 11 34 sorted : 3 5 9 11 18 34 arrayA: 34 arrayB: arrayA: 34 arrayB: 18 arrayA: 34 arrayB: 18 11 arrayA: 34 9 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 3 at this point all values are read and both sets have same no. of elements now sum of arrayA = 48 now sum of arrayB = 32 diff of sum = 16 half of diff = 16/2 = 8 (we consider integer values only) now try to find one no. in both the array with their diff = 8 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) the two no. are 9 in arrayA and 3 in arrayB replace these two, so now we have: arrayA: 34 3 5 arrayB: 18 11 9 now sum of arrayA = 42 now sum of arrayB = 38 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff = 4 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) We can not found any such two no. in these two arrays, thus the given subsets is the solution: arrayA: 34 3 5 arrayB: 18 11 9 - I have tried this algo on various size of arrays with all sort of values and it seems to be working as expected. -Sachin -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Puzzle Will Stuck
Generalization algorithm for the 8 - queens classical chess problem On Jan 4, 5:43 am, bittu shashank7andr...@gmail.com wrote: There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles Note 1: Can be done in O(N^2) time and O(1) space. Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] tarjan
can someone please share a non-wiki link for tarjan algorithm for strongly connected component . a video lecture link would be really nice .. in case you have understanding of how it works , please share your thoughts -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] tarjan
http://forums.topcoder.com/?module=ThreadthreadID=687648messageID=1288196mc=6view=tree#1288196 hope it helps On Tue, Jan 4, 2011 at 10:27 PM, MAC macatad...@gmail.com wrote: can someone please share a non-wiki link for tarjan algorithm for strongly connected component . a video lecture link would be really nice .. in case you have understanding of how it works , please share your thoughts -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Dynamic Programming
Yuckdonald's is considering opening a series of restaurants along Quaint Valley Highway (QVH).The n possible locations are along a straight line, and the distances of these locations from the start of QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The constraints are as follows: 1)At each location,Yuckdonald's may open at most one restaurant.The expected profi t from opening a restaurant at location i is pi, where pi 0 and i = 1; 2; : : : ; n. 2)Any two restaurants should be at least k miles apart, where k is a positive integer. Give an effi cient algorithm to compute the maximum expected total pro fit subject to the given constraints. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] XOR Rounds
http://www.codechef.com/problems/RESN02/ someone please tell me how to approach this problem -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: XOR Rounds
There is a period. Find it and simulate the process only for this value. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: XOR Rounds
There may be long periods. So another approach should be applied. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: XOR Rounds
XOR is associative and commutative. So it's similar as + operator. First turn the array into a n*1 vector. Each round of the operation could be interpreted as a transition matrix A*vector. For example, suppose you have a 4 elements array (a,b,c,d )intially, then one round of operation could be interpreted as: |1 1 0 1 || a | |1 1 1 0 || b | |0 1 1 1 |* | c | |1 0 1 1 || d | When doing the matrix multiply, replace + as XOR replace value multiply as exponential. For example, a+b in the matrix operation should be a XOR b. while 3*a should be interpreted as a XOR a XOR a. Thus the question is equivalent to find out A^k * (initial vector). You can compute A^k easily in logk time. Thanks Yq On Tue, Jan 4, 2011 at 12:16 PM, juver++ avpostni...@gmail.com wrote: There may be long periods. So another approach should be applied. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: XOR Rounds
It can be solve using fast matrix exponentiation (modified version, based on XOR operation). Simulate XOR rounds one-by-one using variables, and you'll see that there is pattern of matrix which is move. Start from vector B = [1, 1, 0, ..., 1]. Then do the following process: next[i] = XOR (prev[j] B[(i + j) % n]) k times. Then multiply (the same operation) result by the array A. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: XOR Rounds
Your matrix has n*n dimensions. So to multiply it, you need to do O(N^3) operations which is too slow for N=500. There is similar approach with a vector multiplication instead of your idea. Btw, it is reached from the same algorithm. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Solving a cubic equation with Cardano's formula
Hi everyone, I'm trying to implement a general method to find the roots of a cubic equation. The conditions are: real coefficients, find all roots: real and complex. I'm using the Cardano's Formula, available here: http://www.engr.mun.ca/~adluri/courses/num_meth/General/Solution_to_cubic_equation.pdf And using the De Moivre Formula to obtain the cubic roots for the numbers (the complex intermediate numbers). http://en.wikipedia.org/wiki/De_Moivre%27s_formula The implementation is in this spreadsheet, attached in this group (file cubic.xls). It runs in Excel or OpenOffice Calc. There's no macro. I only used cell formulas. I just can't understand when I need to calculate the cubic roots using k=0, k=1, k=2 , on the De Moivre's formula. The spreadsheet is very simple to understand. To test the formula, I enter the roots, and it calculates the coefficients and then calculates the roots from them. The result is in the table above, with the roots labeled with 1, 2 and 3. The problem is: - When the roots are 1,2,2 the roots are in k=1, and the roots for k=0 and k=2 are completely wrong; - When they are 1,1,2 the roots are in k=0; - When they are 1,1.0001,2: k=1; - When they are 1,1.01,2: k=2. How can I know when to use k=0, 1 or 2? There must be some way to make a general formula. When the formula is presented anywhere, it seems to be general. Am I doing something wrong? I used Excel just because it's better to visualize. After, I want to implement it in a better language. I don't want to be dependent of any program or library, I want to program the whole method. I can't use a numerical method, because I need to optimize computation time, and I need to have guaranteed convergence. I also want to work with the complex numbers in some way that I can separate its parts (as I did in the spreadsheet), not needing to have a program or library to deal with complex numbers. I appreciate if someone can help me solving this -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Puzzle Will Stuck
ankur is right this problem is similar to the problem of converting a matrix to zero matrix On Tue, Jan 4, 2011 at 8:36 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: how are they similar ? On Tue, Jan 4, 2011 at 8:31 PM, jennmeedo jennme...@gmail.com wrote: Generalization algorithm for the 8 - queens classical chess problem On Jan 4, 5:43 am, bittu shashank7andr...@gmail.com wrote: There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles Note 1: Can be done in O(N^2) time and O(1) space. Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Interview question amazon
problem has many properties like its a BST with parent pointer we shud think of such a solution which uses its both property If we will think abt the brute force recursive solution its complexity will be O(no_of_nodes*height) which can be made more efficient by putting some restrictions in each recursion sum s remaining sum rs if node.value rs/2 then search in left subtree for rs-node.value and s if node.value rs/2 then search in both subtree for rs-node.value and s stop recursion if rs-node.value ==0 or node.value=s On Sun, Dec 26, 2010 at 10:38 PM, MAC macatad...@gmail.com wrote: you are given a bst where each node has a int value , parent pointer , and left and right pointers , write a function to find a path with a given sum value. Path can go from left subtree tree , include root and go to right tree as well . we need to find these paths also . 5 1 10 0 2 6 11 so to find 16 we say it is 1 to 5 to 10 -- thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: Divide an array into two equal subsets
@ sunny is there any reason for splitting the array in ur manner ?? and what abt the complexity ?? i think each time u exchange b/w A and B it takes O(n*n) so u have complexity O(no_of_exchanges*n*n) O(n^2) solution sort the array...O(nlogn) S=total sum search for that continous sub array of length n/2 such that |sub-array sum - S/2| is minimumO(n) let the sum of that sub array is subsum if subsum S/2 it means final set may contain elements that are above this sub array now starting from 1st element in sub array check for every number in the upper part with condition subsumS/2 if subsum S/2 do the same for lower part..O(n*n) On Tue, Jan 4, 2011 at 8:09 PM, sunny tiwari_sac...@rediffmail.com wrote: How about this algorithm: 1 sort the given array in ascending order 2 traverse from back that is greater to smaller 3 put the 1st read in arrayA and the 2nd read in arrayB 4 put the 3rd read in arrayB and the 4th read in arrayA (notice we have reverse the order of putting the values) 5 repeat the process from step 3 until you have read all the values 6 find sum of the two arrays arrayA and arrayB (notice at this point all values are read and both sets have same no. of elements) 7 find diff of their sums 8 find half value of the diff calculated say that value is 'x' 9 now try to find one no. in both the array with their diff = x such that greater no. is from arrayA and smaller is from arrayB if sum of A sum of B else viceversa. 10 if you don't find any such two no. then the current values in arrayA and arrayB is the solution we are looking for 11 else just replace two no. find in step 9 and repeat the process from step 6 Let me try to explain the algo with these two examples: Example 1: given:1 7 6 4 9 12 sorted : 1 4 6 7 9 12 arrayA: 12 arrayB: arrayA: 12 arrayB: 9 arrayA: 12 arrayB: 9 7 arrayA: 12 6 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 arrayA: 12 6 4 arrayB: 9 7 1 at this point all values are read and both sets have same no. of elements now sum of arrayA = 22 now sum of arrayB = 18 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff = 2 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) the two no. are 4 in arrayA and 1 in arrayB replace these two, so now we have: arrayA: 12 6 1 arrayB: 9 7 4 now sum of arrayA = 19 now sum of arrayB = 20 diff of sum = 1 half of diff = 1/2 = 0 (we consider integer values only) Thus the given subsets is the solution: arrayA: 12 6 1 arrayB: 9 7 4 Example 2: given:5 18 3 9 11 34 sorted : 3 5 9 11 18 34 arrayA: 34 arrayB: arrayA: 34 arrayB: 18 arrayA: 34 arrayB: 18 11 arrayA: 34 9 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 arrayA: 34 9 5 arrayB: 18 11 3 at this point all values are read and both sets have same no. of elements now sum of arrayA = 48 now sum of arrayB = 32 diff of sum = 16 half of diff = 16/2 = 8 (we consider integer values only) now try to find one no. in both the array with their diff = 8 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) the two no. are 9 in arrayA and 3 in arrayB replace these two, so now we have: arrayA: 34 3 5 arrayB: 18 11 9 now sum of arrayA = 42 now sum of arrayB = 38 diff of sum = 4 half of diff = 4/2 = 2 (we consider integer values only) now try to find one no. in both the array with their diff = 4 with greater no. in arrayA and smaller in arrayB (reason being here sum of A sum of B) We can not found any such two no. in these two arrays, thus the given subsets is the solution: arrayA: 34 3 5 arrayB: 18 11 9 - I have tried this algo on various size of arrays with all sort of values and it seems to be working as expected. -Sachin -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe
[algogeeks] quick sort
how can we make quick sort to run in O(logn) time in worst case?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
