Lokendra Kumar Singh
BAN USERlabeling the nodes will increase the number of trees which can be formed, because the number of permutations will increase as the nodes are distinct on being labeled. the solution in case of labeled nodes is given by Quadruple factorial.
- Lokendra Kumar Singh August 09, 2007u have written "Now for each element a[i], find N-a[i] using binary search.O(log n)"
if there are n elements , and u r doing it for each element,how can it be O(log n), it shud be O(nlogn)
so the correct complexity in worst case is O(nlogn) + O(nlogn) and
not O(nlogn) + O(logn) as has been mentioned.
1) if all shot 4 bullets(not each)
let bullets = X
bullets used = 4
so , X-4 = X/3
solving, we have X = 6.
so original number of bullets = 6
2) if each one shot 4 bullets then
let bullets = X
bullets used = 4*3=12
so , X-12 = X/3
solving, we have X = 18.
so original number of bullets = 18
plz correct it if i m wrong, the cycle may not involve first node....
the algo by tyler seems correct without any memory overhead....
other approaches can be by using hashmap or by associating flag with each node to keep track if a node is already visited or not, although it involves memory overhead.
a) if i m not wrong, the solution to part a) can't be found in O(log n) because the array is not sorted and so u need to visit each number atleast once so theoritically it can't be less than O(n). if its O(nlogn), for this the solution is first sort the array, it takes O(nlogn) time. then follow the solution of part b.
b)assuming that array is sorted in ascending order, take two pointer startp and endp pointing to begining and end of array.
now test
while(startp < endp)
{
if(arr[startp]+arr[endp] == X)
{
list1 = empty
list2 = empty
do
{
add the array index startp in list1
temp = arr[startp]
}while(temp==arr[++startp]&& startp<endp);
do
{
add the array index startp in list2
temp = arr[endp]
}while(temp==arr[--endp]&& startp<endp);
print "any element frm list1 can pair with any element frm list2"
print list1
print list2
}
else if(arr[startp]+arr[endp] < X)
{
startp++
}
else
endp--;
}
Assuming that it is to be implemented using array(question is that way), i think the better solution wud be d combination of ideas from guest(Post 1) and sathesh(Post 11).
take two stacks pointers from left(these moves to right on push)
stact1=for every (i%2==0)
stack2=for every (i%2==0) + 1
and stack3 from end of the array(moves to the left on push)
this way we are utilising the memory more efficiently(we need to check it out if its true bcos it may change depending on how number of elements in each stack grow)
the condition to check if the corresponding stack is full or empty can be changed accordingly.
Adjacency list in case of a sparse graph while adjacency matrix in case of dense graph. check out coreman's algo book.
- Lokendra Kumar Singh July 31, 2007the solution for this is a simple BFS traversal of a tree,can be found in any standard textbook.
- Lokendra Kumar Singh July 31, 2007u can see the solution posted by anonymous in post 2.
- Lokendra Kumar Singh July 31, 2007if no memory overhead required then solution by aditya is best otherwise solution posted by anonymous in post 2 is best in time complexity,although Ved is also trying to do the same thing indirectly but the whole list gets disrupted, logically his algo is also correct.
- Lokendra Kumar Singh July 30, 20071) take a doubly circular linked list, take two pointers(forp and backp) and start from any point, calculate X(Ci-Gi).
2) when moving forward to next station using forp calculate sum = sum + X. if sum is -ve move back using backp and calculate sum = sum + (Ci-1 - Gi-1). continue to move back till sum becomes +ve and then start again moving forward using step 2 itself.
3) when forp equals backp and sum is +ve u have got the starting station else if sum is -ve there is no starting station.
This is a linear time algorithm.
RepSpent 2001-2007 promoting augmented reality integrated through social media in West Palm Beach, FL. Won several awards for merchandising Roombas ...
the list is traversed only once, see only p2 is used for comparison , p1 is simply incremented, computationally it may take less time than traversing the list twice(depending on compiler implementation and value of NULL chosen) but not more.
- Lokendra Kumar Singh September 12, 2007