Re: [algogeeks] Re: amazon q
I m surprised that ur whole explanation is for me :-o Check ur previous post and then last post... i think u r confused On Tue, Aug 23, 2011 at 3:10 PM, WgpShashank shashank7andr...@gmail.comwrote: @sagar, A self-balancing balancing binary search tree(Its *BST not BT )*containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). please note that if it would have been simple BST not Balnced BST then our complexity to lookup will changes to O(n) in worst case when tree is skewed but as question say balanced BST (check out AVL/RB Tree) they gureentte that look-up will O(logn) only why its true will work you need to go through tree rotation (thats used to make tree balanced reduce height ). Since Heap is a balanced binary tree (or almost complete binary tree but not balanced BST ), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapifyhttp://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present because of this constraint we can't use min-heap as well . For a heap, we cannot find out in O(logn) if an element is present or not as its balanced Binary Tree(BT) , we have to search all the elements e.g.in both left right sub-tree up-to leaf so in worst case it will take O(n) time to search an element weather ist present or not , then its present leave it else insert as a last node call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) =O(n) search+heapify =O(search) so why correct answer is only Balanced Binary Search Tree Do Notify me if i missed something or wants more clarification ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/65k0xGJY6ZoJ. 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
Its Both of the BST and Heap... Prem On Tue, Aug 23, 2011 at 5:01 PM, sagar pareek sagarpar...@gmail.com wrote: I m surprised that ur whole explanation is for me :-o Check ur previous post and then last post... i think u r confused On Tue, Aug 23, 2011 at 3:10 PM, WgpShashank shashank7andr...@gmail.comwrote: @sagar, A self-balancing balancing binary search tree(Its *BST not BT )*containing n items allows the lookup, insertion, and removal of an item in O(log n) worst-case time. Since it’s a BST, we can easily find out minimum element in O(nlogn). please note that if it would have been simple BST not Balnced BST then our complexity to lookup will changes to O(n) in worst case when tree is skewed but as question say balanced BST (check out AVL/RB Tree) they gureentte that look-up will O(logn) only why its true will work you need to go through tree rotation (thats used to make tree balanced reduce height ). Since Heap is a balanced binary tree (or almost complete binary tree but not balanced BST ), insertion complexity for heap is O(logn). Also complexity to get minimum in a min heap is O(logn) because removal of root node causes a call to heapifyhttp://www.cs.virginia.edu/%7Eluebke/cs332.fall00/lecture4/index.htm(after removing the first element from the array) to maintain the heap tree property. But a heap cannot be used for the above purpose as the question says – insert an element if it is not already present because of this constraint we can't use min-heap as well . For a heap, we cannot find out in O(logn) if an element is present or not as its balanced Binary Tree(BT) , we have to search all the elements e.g.in both left right sub-tree up-to leaf so in worst case it will take O(n) time to search an element weather ist present or not , then its present leave it else insert as a last node call heapify (take O(logn)) so tottal time complexity will be O(n)+ O(logn) =O(n) search+heapify =O(search) so why correct answer is only Balanced Binary Search Tree Do Notify me if i missed something or wants more clarification ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/65k0xGJY6ZoJ. 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
Ok then answer must be both of them :) actually finding min is O(1) but to re-heapify after deletion is log(n). On Mon, Aug 22, 2011 at 9:55 AM, Amol Sharma amolsharm...@gmail.com wrote: BST should be the answer..agree with the reason by dumanshu -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Mon, Aug 22, 2011 at 6:52 AM, Akash Mukherjee akash...@gmail.comwrote: ay that the re-heapify is implicit just as the re-balance is im -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
@shashank what about min heap? Check this out -- http://en.wikipedia.org/wiki/Heap_%28data_structure%29 On Mon, Aug 22, 2011 at 4:13 PM, WgpShashank shashank7andr...@gmail.comwrote: Only Balanced BST (its guaranteed that we can search element in o(logn) , i am assuming its maxheap .In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n) 12 / \ / \ 8 7 / \ / \ try to search 5 in this using Heap balanced BST / \ / \ 2 3 4 5 As searching is main constraints on complexity we can't use Heap to achieve O(logn) it will take linear time but using Balanced BST (e.g. AVL/RB Tree) we can search element in O(logn) :) Shashank CSE,BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/fmXlF2-kcFwJ. 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
+1 Dumanshu This question was asked by amazon :D And answer is BST only coz deletion in heap(min heap) is O(1). And if it is max heap then deletion of min element is O(n). On Sun, Aug 21, 2011 at 9:13 PM, Dumanshu duman...@gmail.com wrote: We can't use a heap. Balanced BST is correct because Deletion of the smallest element Insertion of an element if it is not already present in the set - for this we need to search for the element and searching in heap is O(n). On Aug 21, 6:16 pm, priya ramesh love.for.programm...@gmail.com wrote: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
@sagar : deletion in logn, check http://en.wikipedia.org/wiki/Heap_%28data_structure%29 i would say that the re-heapify is implicit just as the re-balance is implicit in balanced bst On Mon, Aug 22, 2011 at 12:58 AM, sagar pareek sagarpar...@gmail.comwrote: +1 Dumanshu This question was asked by amazon :D And answer is BST only coz deletion in heap(min heap) is O(1). And if it is max heap then deletion of min element is O(n). On Sun, Aug 21, 2011 at 9:13 PM, Dumanshu duman...@gmail.com wrote: We can't use a heap. Balanced BST is correct because Deletion of the smallest element Insertion of an element if it is not already present in the set - for this we need to search for the element and searching in heap is O(n). On Aug 21, 6:16 pm, priya ramesh love.for.programm...@gmail.com wrote: A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. Deletion of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? · Pick one of the choices A heap can be used but not a balanced binary search tree A balanced binary search tree can be used but not a heap Both balanced binary search tree and heap can be used Neither balanced binary search tree nor heap can be used -- 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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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: amazon q
BST should be the answer..agree with the reason by dumanshu -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99 On Mon, Aug 22, 2011 at 6:52 AM, Akash Mukherjee akash...@gmail.com wrote: ay that the re-heapify is implicit just as the re-balance is im -- 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: AMAZON Q
@Rajeev: How will you update the position of each element in the linked list after removing a particular element? Won't you have to traverse the list completely in which case your algo will be O(n^2) ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Jylnk0KFxy0J. 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: AMAZON Q
@Tayler : That's y i am using Java ArrayList instead of linked list where arrayList maintains element position.But problem is when an element is removed from the list,all subsequent elements to be moved forward Please check javadoc of arrayList : http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html On Thu, Jul 28, 2011 at 11:58 AM, Tyler Durden abhishek.khattr...@gmail.com wrote: @Rajeev: How will you update the position of each element in the linked list after removing a particular element? Won't you have to traverse the list completely in which case your algo will be O(n^2) ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Jylnk0KFxy0J. 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. -- Thank You Rajeev Kumar -- 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: AMAZON Q
@Rajeev: Okay, I am using C which has no such facilities of auto indexing the list.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/BsMmVwxw_T4J. 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: AMAZON Q
Hey ankit, i gave java code also...didn't u check it in the link...anyway i am explaining here. *Note : Position count starts from 0. * *ex: {1,2,3,4} ...position of '1' is zero* * * *In the below approach,we are checking element position in the modified list(after deletion operation in the previous iteration).* given array is : ar[]= {1,3,2,4,5,4,2}. construct a list with array elements and sort it.Now list contains :1,2,2,3,4,4,5 Now traverse through array elements from i=0 to n-1(start to end) store result in result[] array. list is *1*-2-2-3-4-4-5 for i=0, a[0]=1,search for a[0] position in the list(right occurrence).a[0]=1 position in list is '0' add '0' to result.===result[0]=0; remove the element a[0] from the list.now list contains 2-2-*3*-4-4-5 for i=1,a[1]=3,search for a[1] position in the list(right occurence).a[1]=3 position in list is '2' add '2' to resultresult[1]=2 remove the element a[1] from the list.now list contains 2-*2*-4-4-5 for i=2,a[2]=2,search for a[2] position in the list(right occurence).a[2]=2 position in list is '1' add '1' to resultresult[2]=1 remove the element a[2] from the list.now list contains 2-4-*4*-5 for i=3,a[3]=4,search for a[3] position in the list(right occurence).a[3]=4 position in list is '2' add '2' to resultresult[3]=2 remove the element a[3] from the list.now list contains 2-4-5 for i=4,a[4]=5,search for a[4] position in the list(right occurence).a[4]=5 position in list is '2' add '2' to resultresult[4]=2 remove the element a[4] from the list.now list contains 2-*4* for i=5,a[5]=4,search for a[5] position in the list(right occurence).a[5]=4 position in list is '1' add '1' to resultresult[5]=1 remove the element a[5] from the list.now list contains 2 for i=6,a[6]=2,search for a[6] position in the list(right occurence).a[6]=2 position in list is '0' add '0' to resultresult[6]=0 remove the element a[6] from the list.now list is empty. resultant array contains : from all conditions : add '0' to result.===result[0]=0; add '2' to resultresult[1]=2 add '1' to resultresult[2]=1 add '1' to resultresult[3]=2 add '2' to resultresult[4]=2 add '1' to resultresult[5]=1 add '0' to resultresult[6]=0 expected result {0,2,1,2,2,1,0} actual result =={0,2,1,2,2,1,0} I hope u r clear now.Please let me know if you still have doubts... U can execute the java code given in link : http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elements-on-right.html I will be more happy if you give me failed cases... On Wed, Jul 27, 2011 at 11:25 AM, ankit sambyal ankitsamb...@gmail.comwrote: @rajeev :try the example given in the question. And explain ur algo with that example -- Thank You Rajeev Kumar -- 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: AMAZON Q
@vivin : Your algo seems to be wrong. Plz take an example and explain. I may hv misunderstood u .. -- 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: AMAZON Q
* Algorithm : 1)Conside original array a[] 2)Construct a sorted list with the array elements(O(nlogn)) 3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search. -position in the sorted list returns the number of elements in the less than the current element on right side. -after remove the current element from the sorted list. PS: list is preferred datastructure because there are so many insertion and deletion operations. check this link : http://rajeevprasanna.blogspot.com/2011/07/count-number-of-min-elements-on-right.html * On Tue, Jul 26, 2011 at 11:08 AM, ankit sambyal ankitsamb...@gmail.comwrote: @vivin : Your algo seems to be wrong. Plz take an example and explain. I may hv misunderstood u .. -- 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. -- Thank You Rajeev Kumar -- 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: AMAZON Q
@rajeev:ur algo does not give the correct answer. -- 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: AMAZON Q
@bharath :I think array C is not the resultant array. Take an example and explain -- 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: AMAZON Q
@ankit : can u give me a case where it fails... On Wed, Jul 27, 2011 at 8:33 AM, ankit sambyal ankitsamb...@gmail.comwrote: @rajeev:ur algo does not give the correct answer. -- 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. -- Thank You Rajeev Kumar -- 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: AMAZON Q
@ankit : can u give me a case where it fails... On Wed, Jul 27, 2011 at 8:33 AM, ankit sambyal ankitsamb...@gmail.comwrote: @rajeev:ur algo does not give the correct answer. -- 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. -- Thank You Rajeev Kumar -- 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: AMAZON Q
what about precomputation and then binary search...? On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote: @Anyone worked on this before? I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)* I've to prove on this.. If someone have time.. can you *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
its equal to calculating the Fibonacci numbers till we get a number which is closest to and lesser than N...anything better?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: what about precomputation and then binary search...? On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote: @Anyone worked on this before? I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)* I've to prove on this.. If someone have time.. can you *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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: AMAZON Q
if u have many test cases, this approach is helpful. On Tue, May 24, 2011 at 6:42 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: its equal to calculating the Fibonacci numbers till we get a number which is closest to and lesser than N...anything better?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: what about precomputation and then binary search...? On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote: @Anyone worked on this before? I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)* I've to prove on this.. If someone have time.. can you *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
yes, that depends on what limits u have been given. for the unknown one, i ll have to think.. On Tue, May 24, 2011 at 6:48 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Aakash Sir...if it is so, can u elaborate ur logic??i mean what should be maximum limit on the precomputation?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: if u have many test cases, this approach is helpful. On Tue, May 24, 2011 at 6:42 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: its equal to calculating the Fibonacci numbers till we get a number which is closest to and lesser than N...anything better?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: what about precomputation and then binary search...? On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote: @Anyone worked on this before? I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)* I've to prove on this.. If someone have time.. can you *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
suppose its maximum limit is unsigned int onlythen u mean to say we need to precompute till the maximum limit of unsigned which is unnecessary taking up size if we give input say 50 On 5/24/11, Aakash Johari aakashj@gmail.com wrote: yes, that depends on what limits u have been given. for the unknown one, i ll have to think.. On Tue, May 24, 2011 at 6:48 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: @Aakash Sir...if it is so, can u elaborate ur logic??i mean what should be maximum limit on the precomputation?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: if u have many test cases, this approach is helpful. On Tue, May 24, 2011 at 6:42 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: its equal to calculating the Fibonacci numbers till we get a number which is closest to and lesser than N...anything better?? On 5/24/11, Aakash Johari aakashj@gmail.com wrote: what about precomputation and then binary search...? On Tue, May 24, 2011 at 6:37 AM, sravanreddy001 sravanreddy...@gmail.comwrote: @Anyone worked on this before? I'm thinking of a time complexity of *(log N)^2 -- Square of (log N)* I've to prove on this.. If someone have time.. can you *prove that, the T'th fibinocci number is always greater than 'N'* *where T = (log N)^2 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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: AMAZON Q
@all it is simple binary search problem we can write f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get formula when n is odd. f(3), f(4), f(5) f(6) f(6), f(7), f(8) f(12) . . . as soon as you got a fibnocci number greater than n suppose p-- than you have two ranges p, p/2; now apply binary search in range (p/2 p) that is cal f(p+p/2) compare the value from n. accordigly move left or right. till (p - p/2 != 1) solution is o(log(n)); hopefully i am clear. -- 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: AMAZON Q
@ps: no, suppose for given N testcases, get the maximum one, and generate fibs greater than that. and then for others u can get with binary search only, u will have to improve the fib generator, so basically matrix expo, can help. other way of doing this is described in above post. On Tue, May 24, 2011 at 6:52 AM, anshu mishra anshumishra6...@gmail.comwrote: @all it is simple binary search problem we can write f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get formula when n is odd. f(3), f(4), f(5) f(6) f(6), f(7), f(8) f(12) . . . as soon as you got a fibnocci number greater than n suppose p-- than you have two ranges p, p/2; now apply binary search in range (p/2 p) that is cal f(p+p/2) compare the value from n. accordigly move left or right. till (p - p/2 != 1) solution is o(log(n)); hopefully i am clear. -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
@Aakash Sir...can u clarify giving some exampleslike i give input N=10,it should O/P 8if N=51,O/P=34 On 5/24/11, Aakash Johari aakashj@gmail.com wrote: @ps: no, suppose for given N testcases, get the maximum one, and generate fibs greater than that. and then for others u can get with binary search only, u will have to improve the fib generator, so basically matrix expo, can help. other way of doing this is described in above post. On Tue, May 24, 2011 at 6:52 AM, anshu mishra anshumishra6...@gmail.comwrote: @all it is simple binary search problem we can write f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get formula when n is odd. f(3), f(4), f(5) f(6) f(6), f(7), f(8) f(12) . . . as soon as you got a fibnocci number greater than n suppose p-- than you have two ranges p, p/2; now apply binary search in range (p/2 p) that is cal f(p+p/2) compare the value from n. accordigly move left or right. till (p - p/2 != 1) solution is o(log(n)); hopefully i am clear. -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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: AMAZON Q
@bittu: yes, this can be the way. just make ur fib generator faster(using matrix expo.) for less complexity. On Tue, May 24, 2011 at 7:33 AM, bittu shashank7andr...@gmail.com wrote: @all geeks I have already posted it 2-3 forums..here let me post it again its O(n) but the basic idea is clear if got the problem stmt correct then we have to find out the largest Fibonacci number that is small then given number n so say if n=10 then should be 8 for n=13 i=8 n=14 i=13 similarly for all n13 n 21 i will 13 so on i don't why so confusion ?? It Will Cover All Test Cases #includestdio.h int fib(int n) { int final=0,i,c,a=0,b=1; for(i=2;in;i++) { c=a+b; a=b; b=c; if(cn) final=c; } return final; } int main() { int n=14; printf( %d , fib(n)); } TC O(n) SC O(1) Run Here https://ideone.com/aCli7 Optimization: To get the answer in O(logn) we can use matrix representation of Fibonacci number check wiki.. if you wants O(logn) then i can also post that..I hope m clear ..There are already 6 Way Known to me to find nth Fibonacci Number only thing necessary is that optmization .. Correct me if anything wrong ??? Thanks Shashank the Best Way To Escape From The problem is To Solve It CSE,BIT Mesra Reach Me +91-9739002481 -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
U r using he same approach which I mentioned it before...I knew about this approach but it sounded to me too naive solution...so I was thinking whether there exists any shortcurt method/mathematical formulae for it or not.. On 5/24/11, bittu shashank7andr...@gmail.com wrote: @all geeks I have already posted it 2-3 forums..here let me post it again its O(n) but the basic idea is clear if got the problem stmt correct then we have to find out the largest Fibonacci number that is small then given number n so say if n=10 then should be 8 for n=13 i=8 n=14 i=13 similarly for all n13 n 21 i will 13 so on i don't why so confusion ?? It Will Cover All Test Cases #includestdio.h int fib(int n) { int final=0,i,c,a=0,b=1; for(i=2;in;i++) { c=a+b; a=b; b=c; if(cn) final=c; } return final; } int main() { int n=14; printf( %d , fib(n)); } TC O(n) SC O(1) Run Here https://ideone.com/aCli7 Optimization: To get the answer in O(logn) we can use matrix representation of Fibonacci number check wiki.. if you wants O(logn) then i can also post that..I hope m clear ..There are already 6 Way Known to me to find nth Fibonacci Number only thing necessary is that optmization .. Correct me if anything wrong ??? Thanks Shashank the Best Way To Escape From The problem is To Solve It CSE,BIT Mesra Reach Me +91-9739002481 -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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: AMAZON Q
search OEIS.. and tell if you find something interesting :) On Tue, May 24, 2011 at 7:37 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: U r using he same approach which I mentioned it before...I knew about this approach but it sounded to me too naive solution...so I was thinking whether there exists any shortcurt method/mathematical formulae for it or not.. On 5/24/11, bittu shashank7andr...@gmail.com wrote: @all geeks I have already posted it 2-3 forums..here let me post it again its O(n) but the basic idea is clear if got the problem stmt correct then we have to find out the largest Fibonacci number that is small then given number n so say if n=10 then should be 8 for n=13 i=8 n=14 i=13 similarly for all n13 n 21 i will 13 so on i don't why so confusion ?? It Will Cover All Test Cases #includestdio.h int fib(int n) { int final=0,i,c,a=0,b=1; for(i=2;in;i++) { c=a+b; a=b; b=c; if(cn) final=c; } return final; } int main() { int n=14; printf( %d , fib(n)); } TC O(n) SC O(1) Run Here https://ideone.com/aCli7 Optimization: To get the answer in O(logn) we can use matrix representation of Fibonacci number check wiki.. if you wants O(logn) then i can also post that..I hope m clear ..There are already 6 Way Known to me to find nth Fibonacci Number only thing necessary is that optmization .. Correct me if anything wrong ??? Thanks Shashank the Best Way To Escape From The problem is To Solve It CSE,BIT Mesra Reach Me +91-9739002481 -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
yes, as to my knowledge. there's a similar problem on SPOJ also. I can remember that i solved that in similar way (with matrix expo.). If anyone finds better way, please post here. On Tue, May 24, 2011 at 8:02 AM, bittu shashank7andr...@gmail.com wrote: @aakash...so above algo is fine working fine i forget to put else stmt after if otherwise unnecessary comparison so you can add if(finalc)then final=c else break; in above program will post O(logn) program soon Thanks Shashank -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
int fibArray[INTEGER_MAX_VALUE] = {0}; int fibonacci (int n) { if (n = 0) { return 0; } else if ( n 0 fibArray[n] != 0) { return fibArray[n]; } else { if (n == 1) return (fibArray[n] = 1); return (fibArray[n] = fibonacci(n - 1) + fibonacci(n-2)); } } int findNearestFibLessthanK(int k) { int upper = INTEGER_MAX_VALUE; int lower = 0; int incr = 1; int fibLower = 0; while (lower upper) { fibLower = fibonacci(lower + incr); if (fibLower k) { incr = 1; } else if (fibLower == k) { return fibLower; } else { upper = incr; lower += incr 1; incr = 1; } } return fibLower; } Thanks, Immanuel On Tue, May 24, 2011 at 8:09 PM, Aakash Johari aakashj@gmail.comwrote: search OEIS.. and tell if you find something interesting :) On Tue, May 24, 2011 at 7:37 AM, Piyush Sinha ecstasy.piy...@gmail.comwrote: U r using he same approach which I mentioned it before...I knew about this approach but it sounded to me too naive solution...so I was thinking whether there exists any shortcurt method/mathematical formulae for it or not.. On 5/24/11, bittu shashank7andr...@gmail.com wrote: @all geeks I have already posted it 2-3 forums..here let me post it again its O(n) but the basic idea is clear if got the problem stmt correct then we have to find out the largest Fibonacci number that is small then given number n so say if n=10 then should be 8 for n=13 i=8 n=14 i=13 similarly for all n13 n 21 i will 13 so on i don't why so confusion ?? It Will Cover All Test Cases #includestdio.h int fib(int n) { int final=0,i,c,a=0,b=1; for(i=2;in;i++) { c=a+b; a=b; b=c; if(cn) final=c; } return final; } int main() { int n=14; printf( %d , fib(n)); } TC O(n) SC O(1) Run Here https://ideone.com/aCli7 Optimization: To get the answer in O(logn) we can use matrix representation of Fibonacci number check wiki.. if you wants O(logn) then i can also post that..I hope m clear ..There are already 6 Way Known to me to find nth Fibonacci Number only thing necessary is that optmization .. Correct me if anything wrong ??? Thanks Shashank the Best Way To Escape From The problem is To Solve It CSE,BIT Mesra Reach Me +91-9739002481 -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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: AMAZON Q
Ur algo's complexity will not be O(logn)..it will be O(nlogn).. On 5/24/11, bittu shashank7andr...@gmail.com wrote: @piyuesh..i posted the naive because geeks are so confused about this quest. i have seen some geeks saying terrible time complexity of it. so above approach will make 1st of all every1clear optimization 2ndary step... As i have told earlier its similar to find nth Fibonacci number can be done in O(logn) using Matrix Representation that i also know will post later..its little modification of nth Fibonacci number. Thanks Shashank Reach Me +99-9739002481 -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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.