try this : similar problem
http://www.spoj.pl/problems/NOCHANGE/
On Tue, Jun 19, 2012 at 1:32 PM, aditya gupta adityagupta...@gmail.com wrote:
this can be solved in a manner similar to knapsack problem.
u can take the weight of tha knapsack the be the the various amounts u need
to make, 13
#includeiostream
using namespace std;
struct node
{
int num;
int l,r;
node * left;
node * right;
};
node * create(node * root,int start,int end);
node * update(node * root, int i,int j);
int query(node * root,int i,int j);
main()
{
int n,q;
cinnq;
node *
isnt it is similar to coin change problem , here we need minimum
number of stamps to form a value.
so we can check which number exceed the min stamp range i.e 1 to 3.
On Jun 19, 11:55 am, sanjay pandey sanjaypandey...@gmail.com wrote:
The postage stamp problem is a mathematical riddle that asks
Hmmm, true. That's what I expected in this solution. Similarly, we can get
3 by (3,3) (1,2)
However, did you take a look at the other solution I proposed? I guess that
solves the problem to some extent.
On Tue, Jun 19, 2012 at 7:18 PM, Sourabh Singh singhsourab...@gmail.comwrote:
@Umer and
Explain how to implement doubly linked lists using only one pointer value*np[x
*] per item instead of the usual two (next and prev). Assume that all
pointer values can be interpreted as
k-bit integers, and define* np[x] to be np[x] = next[x] XOR prev[x],* the
k-bit “exclusive-or” of next[x] and
I am asking again .. can any one please suggest better method for getting
the median on the longest path of the tree ..
efficient method .
On Tue, Jun 19, 2012 at 5:08 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
for getting diameter we can simply add the max height of left subtree
As you traverse along and find the diameter of the tree, keep track of the
number of nodes thereby traversed. Let that be equal to n.
Now, centre is the node corresponding to floor((n+1)/2).
On Wed, Jun 20, 2012 at 5:19 PM, Nishant Pandey
nishant.bits.me...@gmail.com wrote:
I am asking again
Simple!
Just traverse the doubly linked list and keep track of next and previous of
each node, and do XOR and save the result in a new pointer, what according
to you is np.
Be careful about boundary cases, i.e head and tail, though.
On Wed, Jun 20, 2012 at 5:16 PM, Krishna Kishore
How to reverse a Queue .
Constraints: Time complexity O(n). space complexity: O(1)
--
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/-/kepls-8qRwgJ.
To post to
count the size of queue : O(n)
loop for n and do remove and add in queue : O(n)
Total : O(n)
On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote:
How to reverse a Queue .
Constraints: Time complexity O(n). space complexity: O(1)
--
You received this message because
@Saurabh: queue will be remain unchanged according to your algorithm.
Because if you will delete an element from front and add at rear no change
will be there. After n iteration front will be pointing to same element and
rear will also point to same element.
Correct me if i am wrong. :)
On Wed,
For ex: let only two element are in queue: 1 2 (1 at front and rear is at
2).
looping two times:
first time: delete from front and adding to rear: queue will be: 2 1(front
at 2 , rear at 1)
second iteration: deleting 2 and adding to queue :result will be: 1 2
(front 1, rear 2)
On Wed, Jun 20,
I meant do it for n-1 times (my focus was on time complexity).Try with more
examples and you will know :)
On Wed, Jun 20, 2012 at 6:50 PM, Navin Kumar algorithm.i...@gmail.comwrote:
For ex: let only two element are in queue: 1 2 (1 at front and rear is at
2).
looping two times:
first time:
can we create other methods or we have to use only enqueue and dequeue...?
if yes then simply
for(i=0;i=n/2;i++)
swap(i,n-i);
On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Saurabh: queue will be remain unchanged according to your algorithm.
Because if you will
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue
etc
On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote:
can we create other methods or we have to use only enqueue and dequeue...?
if yes then simply
for(i=0;i=n/2;i++)
swap(i,n-i);
On Wed,
You could use recursion.
def reverse_Q q
if !q.isEmpty?
el = q.dequeue
nQ = reverse_Q(q)
nQ.enqueue el
return nQ
end
return q
end
On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote:
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue
etc
On
@Kirubakaran : still space complexity is O(n) due to stack.Can it be solved
in space complexity O(1).
On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote:
You could use recursion.
def reverse_Q q
if !q.isEmpty?
el = q.dequeue
nQ = reverse_Q(q)
nQ.enqueue el
Why will my proposed solution not work for you ???
On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Kirubakaran : still space complexity is O(n) due to stack.Can it be
solved in space complexity O(1).
On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D
@saurabh : i want solution with space complexity of O(1) . your solution is
right but it takes O(n) space.
On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote:
Why will my proposed solution not work for you ???
On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar
How ??
I am asking to manipulate the same queue.
Dequeue n-1 elements and enqueue them in order to you take out to the same
queue..Where is extra space involved ?
On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@saurabh : i want solution with space complexity of O(1)
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will take
O(1) time but you have to enqueue elements in reverse order.Not in the
order you fetched. Think about it :). Then you have to take stack or some
other data structure.
On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh
My bad...Sorry :(..Yes it certainly was not right
On Wed, Jun 20, 2012 at 8:56 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will
take O(1) time but you have to enqueue elements in reverse order.Not in the
order you fetched.
@Navin: as you say you have to take stack or some other data structure
then it will definately not be donw in O(1) space complexity i think the
recursive solution is best because we are not explicitly using any extra
space its internal stack is using this space.
--
You received this message
@Rishabh: i know using stack or recursion it can be done easily with O(n)
space. I want to know whether there exist more space efficient algo for
this problem or not?
On Wed, Jun 20, 2012 at 9:20 PM, Rishabh Agarwal rishabh...@gmail.comwrote:
@Navin: as you say you have to take stack or some
Queues are basically linked lists with head and tail pointers. It is
possible to reverse the list by change of pointers in O(n) time n O(1)
space.
PS: Not considering queue ADT with enqueue dequeue operations.
On Wednesday, 20 June 2012 18:34:46 UTC+5:30, Navin Kumar wrote:
How to reverse a
void Reverse(std::queueint pQ)
{
if(pQ.empty())
return;
int item=pQ.front();
pQ.pop();
Reverse(pQ);
pQ.push(item);
}
Regards
On Wed, Jun 20, 2012 at 9:41 PM, enchantress elaenjoy...@gmail.com wrote:
Queues are basically linked lists with head and tail pointers. It is
possible to reverse the
Just a query :
If the queue is implemented as an array, then is it not possible to swap
the elements from the last and first position onwards until you reach
middle point. Wont this use O(1) space and O(n/2) time.
On Wed, Jun 20, 2012 at 1:56 PM, Hassan Monfared hmonfa...@gmail.comwrote:
using recursion,
reverse(queue,front,rear) {
if( front rear ) {
swap( queue[front], queue[rear] );
reverse( queue, front+1, rear-1);
}
}
On Wed, Jun 20, 2012 at 11:53 PM, Sreeprasad Govindankutty
sreeprasad...@gmail.com wrote:
Just a query :
If the queue is implemented as an
void make_group( int a[], int size) {
int j = 0;
for ( int i = 0; i size; i++ ) {
if ( a[i] 0 ) {
swap(a[i],a[j]);
j++;
}
}
}
--
Akshat Sapra
Under Graduation(B.Tech)
IIIT-Allahabad(Amethi Campus)
Abhishek Sharma : swap is not allowed because you can push at only one
side of queue.
it's not dequeue.
On Wed, Jun 20, 2012 at 11:21 PM, Abhishek Sharma abhi120...@gmail.comwrote:
using recursion,
reverse(queue,front,rear) {
if( front rear ) {
swap( queue[front], queue[rear] );
@atul if range is high den complexity wud be much larger...
--
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
i am using long long but still getting WA.
here's my code
#includestdio.h
#includeconio.h
int main()
{
long long cand,sum;
int T,N,i,j,temp[10];
scanf(%d,T);
sum = 0;
for(i=0;iT;i++)
{
scanf(%d,N);
for(j=0;jN;j++)
{
long long not require in this que .
try it again..
--
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
still getting the WA .
is there any test case i am getting wrong?
--
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
here is my code u can check that..
http://ideone.com/Gii1d
--
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
Hi,
It looks like, The interviewer is expecting MinHeap from you,
If modification to array is permitted just build the heap in place (from
end bubbleUp n-1 time) and extract K elements in sorted order
Otherwise you need minimum O(K) memory
Again if you want to use the quick-sort, I
i doesn't seem possible without using stack...
On Wed, Jun 20, 2012 at 10:13 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Rishabh: i know using stack or recursion it can be done easily with O(n)
space. I want to know whether there exist more space efficient algo for
this problem or not?
*np *is nothing but *next_pointer. np[x] *does mean *x-np *which is the
next pointer to node. Actually I am thinking in this way about *np, *that
it stores the *XOR* value of *next* and *prev* pointers.Or Since *np *is a
k-bit integer, the first k/2 bits wil be used for *next*, and other k/2
@saurabh : your solution require O(n) space.
On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote:
How ??
I am asking to manipulate the same queue.
Dequeue n-1 elements and enqueue them in order to you take out to the same
queue..Where is extra space involved ?
On
@mayank:
For each testcase sum is not zero make sum=0 inside the for loop
--
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
oh i am really sorry
the problem is CANDY III
can you help me regarding that
once again sorry
--
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
41 matches
Mail list logo