Mohan
BAN USERLet us take the Anonymous example {2, 6, 7, 4, 10, 8}
Sorting in O(nlgn) will result into {2, 4, 6, 7, 8, 10}
1. Start from the first element 2 and sum it with rest of the elements in loop
e.g. 2 + 4 = 6 (Here search for the sum 6 only after the indices of 2 and 4 and only till the sum becomes less than an element in the array i.e. no need to search beyond 3rd position. In this case we have found 6. If the sum is more than the last element in the sorted array then go ahead)
2. 2 + 7 = 11 (Just look if it is less than highest element in array otherwise go ahead)
3. 2+ 8 .....
After summing first element with rest of the elements then sum the second element with element starting from 3rd position no need to try with first element again.
I think the above two points add to optimizing the approach. But have to calculate the complexity of it.
Anonymous has raised a valid question. I think instead of chars we can assume that we have different set of numbers and focus on the logic of pairing up things in the required manner.
Consider the following example where n(=12) is an even number
e.g. 1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l
step 1: for the first n part do not move the even positioned elements and for the next n part do not move the odd positioned elements.(i.e. 1_3_5_7_8_9_11_ _b_d_f_h_j_l) but interchange the even positioned elements of the first n part with the odd positioned elements of the second n part which results into the following sequence. 1 a 3 c 5 e 7 g 9 i 11 k 2 b 4 d 6 f 8 h 10 j 12 l, which can be viewed as pairs indicated below
(1 a) (3 c) (5 e) (7 g) (9 i) (11 k) (2 b) (4 d) (6 f) (8 h) (10 j) (12 l)
Step 2: Apply the same pairing logic as described above fix the odd positioned pairs in the first n-element array and even positioned elements in the second n-element array and exchange the rest will result into the following
(1 a) (2 b) (5 e) (6 f) (9 i) (10 j) (3 c) (4 d) (7 g) (8 h) (11 k)(12 l)
Now this can be viewed by pairing up four elements togeher in the following way
(1 a 2 b) (5 e 6 f) (9 i 10 j) (3 c 4 d) (7 g 8 h) (11 k 12 l)
step 3: Do the same thing like fixing the odd positioned elements in first half and even positioned in the second half and exchange the rest
(1 a 2 b) (3 c 4 d) (9 i 10 j) (5 e 6 f) (7 g 8 h) (11 k 12 l)
step 4: Pair up the adjacent elements again to result into the following
(1 a 2 b 3 c 4 d) (9 i 10 j) (5 e 6 f 7 g 8 h) (11 k 12 l)
step 5: Apply the same logic again and you will end up with the result
(1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9 i 10 j 11 k 12 l)
Logic needs to be changed a little bit in when n = odd number and I am working on it.
But there is a lot of overhead of exchanging elements if anybody can come out with some insight to overcome this pls discuss it. Thank you.
If symmetry is on root. Do inorder traversal on the entire tree. While doing inorder traversal on the left subtree below the root put the elements inside a stack. While doing inorder traversal on the right subtree below the root compare it with every top element of the stack. At the end if the stack is empty and tree traversal is also completed. Then the tree is symmetrical on root. This should be applicable for any ordered tree
- Mohan February 22, 2008
Count sort also seems a reasonable approach...but if the range of numbers is too large then the amount of the space consumed by the intermediate array to keep the number of occurrences of an element in the array will become large
- Mohan June 10, 2008