for 2nd part of 1st question, when array has become sorted
for ex: 3 5 10 16 17 35 40 56 67 and num is 33
becomes : 3 5 10 16 16 ..
make array of 17 elements s[0,0,1,2..]
s[16] = 2 means we find a duplicate hense resultu
int m = (num%2==1)?(num/2+1):(num/2)
for (int i=0;im){arr
push(), pop() method as stack, and also has a getMinElement(). Require that
getMinElement() is constant time but push()/pop() do not have to be constant
time at first. Then for improvement, these three methods are all required to
be constant time
Define node as
struct node{
int data;
int cu
@juver++ :
I don't think it will work in O(1) time. Plz post ur algo. I may
have misunderstood u !!!
On Tue, Jun 28, 2011 at 11:37 PM, juver++ wrote:
> @samby
> There is no need to use any other data structures but only stack. Each of
> its nodes is a pair of a data and minimal element below
@samby
There is no need to use any other data structures but only stack. Each of
its nodes is a pair of a data and minimal element below the current node.
Then all updates are done in constant time.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" g
No, its not. See carefully...After push or pop, we have to modify
the heap using min heapify function which takes O(log n) time
On Tue, Jun 28, 2011 at 11:21 PM, juver++ wrote:
> pop() and push() are O(1) both in this algo.
>
> --
> You received this message because you are subscribed to the
pop() and push() are O(1) both in this algo.
--
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/-/dbfa0H-3n38J.
To post to this group, send email to algogeeks@go
@ankit,sunny : thanks for the explanation. I got it.
On Wed, Jun 29, 2011 at 10:16 AM, Ashish Goel wrote:
> pointer to next smallest will not lead to constant time operation
>
>
>
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
>
pointer to next smallest will not lead to constant time operation
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Tue, Jun 28, 2011 at 3:19 PM, Anurag Sharma wrote:
> for second problem, you can create a stack of having each element as a nod
Improvement of my solution to second question :
Instead of forming a linked list ,take a heap of the pointer of all
elements in the stack. Apply min heapify to the heap using value to
which the pointer points as the key.
Clearly getMinElement() O(1)
push()-
For the second question have a stack as usual, but have a pointer for
each stack entry. Have a head pointer which points to the minimum.
These pointers point in the sorted order. This is explained by the
following example.
Suppose the elements are pushed in the following order : 3,6,1,8,2.
Then the
@Shachindra: The second part of my solution can definitely be done in
O(n) time . Take 2 pointers : one pointing to the start of the array
and the second pointing to the end of the array. If sum of these 2 is
less than the required sum, increment the first pointer else increment
the second pointer
2nd part of ankit's solution can be easily done in O(n)
after sorting of array
i = 0, j = n-1
while(i < j)
if a[i]+a[j] == x , i and j are indexes of the elements
if a[i]+a[j] > x decrement j
if a[i]+a[j] < x increment i
On Tue, Jun 28, 2011 at 6:49 PM, Shachindra A C wrote:
> @sagar : oops ! N
@sagar : oops ! No need of sorting. Thank you for pointing out :)
On Tue, Jun 28, 2011 at 6:41 PM, sagar pareek wrote:
> @Shachindra
> If you are using binary tree then why are you doing sorting first?
>
> @ANKIT
> Yes you can't do searching of sum of two numbers in less then O(n*n).
>
> On Tue
@Shachindra
If you are using binary tree then why are you doing sorting first?
@ANKIT
Yes you can't do searching of sum of two numbers in less then O(n*n).
On Tue, Jun 28, 2011 at 6:23 PM, Shachindra A C wrote:
> @ankit : I'm pretty confident that the second part of your solution cannot
> be do
@ankit : I'm pretty confident that the second part of your solution cannot
be done in O(n) time. Correct me if I am wrong!! Nevertheless, the overall
time complexity remains O(n*log(n)), as you pointed out.
On Tue, Jun 28, 2011 at 5:59 PM, Shachindra A C wrote:
> @Ankit
> Can you please explain t
@Ankit
Can you please explain the method to get the answer to the second subpart of
your solution in O(n) time?
My solution to solve the problem in O(n log(n)) time is as follows:
Insert the nodes of the sorted array into a binary tree. Then start with the
first node. Subtract the value of the no
Can you please explain how to solve the 2nd question?
--
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/-/5C-1NnideVgJ.
To post to this group, send email to alg
For 1st question :
First sort the array. O(n*logn)
then we can easily find 2 elements in the array which sum to X.
---O(n)
So, Time complexity of the algo : O(n*logn)
Question 2 is trivial..
On Tue, Jun 28, 2011 at 2:30 AM, vikas wrote:
> 1.Given an array o
for second problem, you can create a stack of having each element as a node
having the current value as well as pointer to the next smallest value
present below it. This can solve all 3 operations in constant time.
Thanks,
Anurag
On Tue, Jun 28, 2011 at 3:00 PM, vikas wrote:
> 1.Given an array
1.Given an array of integers and another integer X - create an algorithm to
determine if the sum of any two integers in the array would result in x
2. design a ADT to implement push(), pop() method as stack, and also has a
getMinElement(). Require that getMinElement() is constant time but
push(
20 matches
Mail list logo
