ardent.1981
BAN USERDefinitely not better than O(N*N) but one more solution to this problem:
A) Sort the array.
B) Now start from 3rd element (Lets keep the current pointer to third element)
- Keep two pointers. One at the beginning and one before the current element.
For example if we are at position 10. Then lets have a low pointer pointing
to first number and high pointer pointing to number 9. Check if
sqr(current) = sqr(low) + sqr(high) i.e. in this case : sqr(10th) = sqr(1st) + sqr(9th).
- if sqr(10th) = sqr(1st) + sqr(9th) then we have got the triplet, move current to 11th element.
- If sqr(1st) + sqr(9th) > sqr(10th) then decrease high and do the same ...
- If sqr(1st) + sqr(9th) < sqr(10th) then increase low and do the same ...
This logic is similar to finding two numbers in a sorted array whose sum is a given number.
The sorting will take O(N LOG (N)). Remaining logic should take O(N*N).
After strcat(), the next character to amazonhyd will be'\0'. So there should not be any issue and we will print amazonhyd as output.
Checking the malloc's return address and freeing the memory seems to be the missing part here.
Please free to provide your suggestions.
Logic:
Get the length of both the lists.Let it be x1 and x2.
Lets say y = x1 - x2. Assume x1 > x2.
Skip y nodes of first list. And add the corressponding
nodes of both the lists. Record the positions
where carry is generated.
Now:
While(strcuture for carry is NOT empty)
{
Traversal the bigger list.
Assume we are processing node
at the ith position and there was a carry in the i+1th
position in the carry structure.
Then add 1 more to the sum.
Store the sum in the ith node of first list.
If the sum > 10 then store carry for ith position.
}
Example: No carry Best case.
9->6->5->2
2->3.
x1 = 4, x2 = 2.
There will not be any carry and in only one pass of above while loop
we will get
9->6->7->5.
Example:
9->6->5->2
7->9.
In the first pass: 9->6->2->1 The carry would be 0011. It means that
the carry is generated at 3rd and 4th position.
In the second pass: 9->7->3->1. The carry structure is empty so exit.
Example:Special case.
9->9->9->7
9->9
In the first pass: 9->9->8->6. Carry:0011.
In the seond pass:9->0->9->6. Carry: 0100.
In the third pass: 0->0->9->6. Carry 1000
Special case: Allocate one head node with value:1
So the op will be 1->0->0->9->6.
The complexity will depend upon how many times there is still
a carry left. The number of nodes to visit in any pass would ALWAYS
be less than the number of nodes of previous passes.
Because assume if carry structure is 011100 then in the current
pass I only need to visit till 3rd node {The index of last 1 =3}.
Thus in the next pass, I would always need to visit less than 3 nodes.
@Kyle.
- ardent.1981 September 06, 2011The approach will only work if the duplicate elements are always together as mentioned in the example. However it is not explicitly mentioned in the question. So if the sequence can be 111122223333311111 then you will op 1 multiple times. In that case, bitmap/hash can be used.