use a stack for this
{
//let preorder traversal of a tree be in a array t
for(i = t.length; i-1; i--){
if(t(i) == L){
stack.push(t[i]);
}else{
leftChild = s.pop(); // will return null if stack is empty
rightChild = s.pop(); // will return null if stack is empty
node = new Node(leftChild,
I gues jalaj's solun works perfect.
Thanks and regards,
Gajendra Dadheech
On Sun, Feb 6, 2011 at 4:06 PM, jalaj jalaj.jaiswa...@gmail.com wrote:
use a stack for this
{
//let preorder traversal of a tree be in a array t
for(i = t.length; i-1; i--){
if(t(i) == L){
stack.push(t[i]);
My solution in more detail (in words ):-
start from the end if you get an L
make a node with data L and push its pointer in stack,
if you get a M pop two elements from stack
make them left and right children of M and then push
back m's pointer to stack(if stack is empty then stack returns NULL
but the tree can be created from a preorder walk is more than 1 right? so
the question only ask for 1?
On Feb 6, 2011 7:31 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
My solution in more detail (in words ):-
start from the end if you get an L
make a node with data L and push its pointer
no unique tree will get created i think .. as first popped is left child and
second popped is right child in algo
On Sun, Feb 6, 2011 at 10:29 PM, yq Zhang zhangyunq...@gmail.com wrote:
but the tree can be created from a preorder walk is more than 1 right? so
the question only ask for 1?
On
it can be done in greedy
#includestdio.h
#includeiostream
#includestack
using namespace std;
int main()
{
int n,i,j,count=0;
scanf(%d,n);
int a[n+1],set=0;
a[0]=-1;
for(int i=1;i=n;i++)
scanf(%d,a[i]);
stackint s;
i=1;
j=n;
while(j!=1)
{
set=0;
for(i=1;i=n;i++)
{
if(j-i=a[i])
{printf(%d,i);
j=i;
here is Working Code Without DP in which we need To Find Out Minimum
Jumps for every Jumps its Finding Maximum Step That Can Be Cover In
A Jump So that No. of Jumps Required is Minimized..
#includestdio.h
int main()
{
int arr[]={1 ,3, 5 ,8, 9, 2, 6 ,7 ,6, 8, 9};
int
http://coders-stop.blogspot.com/2010/12/minimum-number-of-jumps.html
--
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
@avi
regarding ur statement...
3, 5, 3, 4, 1, 3, 4, 5
in the above, the greedy would take 3 - 5 - 4 ( 3 steps)
whereas DP would take 3, 4 ( 2 steps)
it depends on what you are greedy about... as i had mentioned earlier,
your algorithm should be greedy on how far the value you choose will
let
@svix that is precisely the reason why i gave my greedy approach first and
then the pseudo code and then the example, also I mentioned that greedy can
be be of different *locally optimal policies* so they *may* have a higher
running time than the corresponding DP solution.
regarding your
@avi... i didn't quite fully understand the intent of the comment... u
had initially said greedy would make wrong choices 3-5-4 and hence
give wrong minimum number of jumps while DP would give 3-4... hence i
responded saying that if we go greedy on a different function, greedy
will yield the right
Sry I misunderstood your comment. I don't feel the greedy solution which
you gave will work in all the cases. Will update the thread when I next
sleep over it.
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the
actually, there is a way t do this in greedy... instead of taking the
local maximum value v for an index i, take the local maximum f(v) = i
+ v... this will get you the right answer...more efficient than DP?
that i'm not sure... but average case will be close to linear
On Jan 14, 9:29 pm,
@svix, I think pacific means takes i+v, But it still won't give the
global optimal
@Avi, I am not an expert on greedy algorithm and some problems may be
solved by using greedy. But as far as I understand, the difference
between DP and Greedy is DP makes use of the solution of the
subproblems
@jammy Thanx for the elongated description :)
Yes, I feel I probably gave a DP solution wrongly to the Greedy approach.
But just to clarify, Greedy does not solve any subproblems, it just makes a
locally optimal choice and proceedes towards a global optimal strategy. And
your point that greedy
thinkin abt this again, there may be a slight problem with
straightforward greedy...
note that reaching 0 doesn't let u move forward...
On Jan 15, 12:54 pm, Avi Dullu avi.du...@gmail.com wrote:
@jammy Thanx for the elongated description :)
Yes, I feel I probably gave a DP solution wrongly to
The greedy will always chose the maximum, so iff a 0 is chosen, that implies
one cannot reach the end of the array.
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they
I don't think the inner loop is executing only once . Kindly check it for
this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop
you will find that for same values of i(Outer index) inner loop is called.
Its an O(n2) solution .
--
You received this message because you are
I guess u got confused with the comment I wrote, I have added 2 print
statements and now I guess it should be clear to you as to why the code is
O(n). The comment means that each element of the min_steps_dp will be
ACCESSED only ONCE over the execution of the entire program. Hence the outer
loop
@Avi Greedy approach doesn't work since you can't ensure the choice is
locally optimum. Consider 3,9,2,1,8,3. Using greedy alg. would give
you 3,1,8,3 while otherwise DP would give you 3,9,3.
On Jan 14, 6:11 am, Avi Dullu avi.du...@gmail.com wrote:
I guess u got confused with the comment I
@jammy Even I felt the same, but the greedy 'algo' u suggest is actually
IMHO not a greedy approach. You just take each arr[i] and jump *without
deciding a locally optimal policy* . SO, if u were to *see* arr[i] and
*decide* on the optimal policy I feel one would follow d same steps as in a
DP
At each location if the value is k ,
find the largest value in the next k elements and jump there.
This greedy approach works in 0(n^2) and i believe it works. If not can
someone give me a counter example ?
On Sat, Jan 15, 2011 at 3:30 AM, Avi Dullu avi.du...@gmail.com wrote:
@jammy Even I
@pacific..
the approach needs a little bit of tuning...
for instance, for the set 9 8 7 6 5 4 3 2 1 1 2, per ur approach, u
will pick 9, 8, 7, 6 etc...
minimum jumps in reality is from 9 to 1 to 2.
On Jan 14, 8:19 pm, pacific pacific pacific4...@gmail.com wrote:
At each location if the value
doesn't greedy approach work here ?
On Sun, Jan 9, 2011 at 8:00 PM, juver++ avpostni...@gmail.com wrote:
It doesn't matter how to make transitions: from current position make all
necessary moves,
or determine all positions from which we can achieve i-th position.
So your method is only the
No, there is a counterexample fot the greedy.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
@juver++ : what is the greedy approach one could take here? I know it would
be wrong, but I tried to come up with a test case for greedy failure, but
realized the greedy policy here will be equivalent to the dp.
@Decipher: your's seems to be a O(n^2) solution. Here in the O(n) version of
it.
It doesn't matter how to make transitions: from current position make all
necessary moves,
or determine all positions from which we can achieve i-th position.
So your method is only the one of possible.
--
You received this message because you are subscribed to the Google Groups
Algorithm
Simple DP, dp[i] - minimum number of steps to reach position i. Then apply
simple transitions: dp[i + step] = min(dp[i + step], dp[i] + 1), step =
a[i].
Something in this way.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
updated :)
Given a boolean matrix with all the true elements on left side in the row so
that each row can be broken into two parts left part containing only true
elements and right part containing only false elements. Find the row with
max number of true elements in it.
00011
0
1
O(m+n).
Search from rightmost top corner. Count the no of zero from right and go to
left, i.e. traverse through columns from right of the first row. When you
find a column having 0, go down to lower row. Check the correspondent column
is 1 or not. If it is, follow the above step or else go down to
@SoumyaNice Solution.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
@shiva , U didn't check for the cycles.Since in question it is never
mentioned about cycles u can add few steps to check cycles.
(eg)
1 3 - 5
| |
| |
| |
4-3--3
--
You received this message because you are subscribed to the Google Groups
Algorithm
oh thank u :)
On Dec 22, 11:20 am, bittu shashank7andr...@gmail.com wrote:
Xcellent Shiva..keep goin on..\
Best Regards
Shashank Mani Narayan
BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
ya through down pointer we can print..coz each time i m making fwd as
NULL
On Dec 20, 2:33 pm, Rishi Agrawal rishi.b.agra...@gmail.com wrote:
See inline ..
On Sat, Dec 18, 2010 at 12:09 PM, siva viknesh sivavikne...@gmail.comwrote:
Given a linked list structure where every node
Xcellent Shiva..keep goin on..\
Best Regards
Shashank Mani Narayan
BIT Mesra
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
It can be done easily by counting sort
On Wed, Dec 15, 2010 at 5:36 AM, Soumya Prasad Ukil
ukil.sou...@gmail.comwrote:
Have a look : http://geeksforgeeks.org/?p=1488
On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote:
@ Bittu:
Lets analyze your code with
use a dictionary (available in C#... basically a collection of generic
key-value pairs where the key lookup is O(1) - hashed internally)
since number that occurred first should be listed first when
frequencies are the same, u need to record the first occurrence of
each number as well. Hence, the
@ankur,saurabh,soumya..
ya ankur i forget to remove range from dare also no need to find
range for this..\
put size-1 intead of range so that malloc will alocate the memory to
all elements in array ..no hope its fine...
what i did is that
i took counter array thta cvontains the no of
Have a look : http://geeksforgeeks.org/?p=1488
On 15 December 2010 05:19, Saurabh Koar saurabhkoar...@gmail.com wrote:
@ Bittu:
Lets analyze your code with iterations:
the array contains 1 3 3 1 2 3 5 2 3
count contains 0 2 2 4 0 1 0 0 0
now 1st iteration:
i=8,7,6 the inner loop
you can use hash table for this dude.
On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote:
given some positive numbers
output the numbers in decreasing order of frequency..in case of a tie
print the number which occurred first
for eg: 1,3,3,1,2,3,5,2,3
the output should be 11225
--
@sajj: if the range of number is not given then ?
On Tue, Dec 14, 2010 at 11:41 PM, sajj sajjv...@gmail.com wrote:
you can use hash table for this dude.
On Dec 14, 8:22 pm, Prims topcode...@gmail.com wrote:
given some positive numbers
output the numbers in decreasing order of frequency..in
what you can do is create a vector pairint,int and sort it on the
baisis of secondary key where it will be it's frequency. if tha range
is not given. If the range is in permissible limits, then hash table
is the answer. I suppose.
On Tue, Dec 14, 2010 at 11:45 PM, Ankur Khurana
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int array[]={1,3,3,1,2,3,5,2,3};
int size=sizeof(array)/sizeof(int);
int min,max;
max=min=array[0];
int i=0;
for(i = 1; i size; i++)
{
if (array[i] min)
min = array[i];
else if (array[i] max)
bittu, in stead of writing your code, put your logic here. It is not the
place to show how capable one is to write a program.
On 14 December 2010 11:00, bittu shashank7andr...@gmail.com wrote:
#include stdlib.h
#includestdio.h
#includeconio.h
int main()
{
int
I think ankur khanna's solution is appropriate. couldn't get what bittu was
trying to do completely.. could you just explain it once please!
On Wed, Dec 15, 2010 at 10:35 AM, Soumya Prasad Ukil
ukil.sou...@gmail.comwrote:
bittu, in stead of writing your code, put your logic here. It is not the
@gene: can you do dry run a test case:
a[0]-a[n-1]
0 1 2 31 34 135
and if u c
On Tue, Dec 7, 2010 at 8:55 AM, Gene gene.ress...@gmail.com wrote:
I should have mentioned that this problem only makes sense if the
array values must be unique.
On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com
@Divesh I have updated my algo and Array A[1,2,3.n] is sorted with
unique elements.CALL FIND_EQUAL(A,1,n)
int FIND_EQUAL(A,start,end)
1.Go to the middle element
2. If A[mid]mid)
3. if(start==mid)
4 return mid-1;
5return FIND_EQUAL(A,1,mid-1);
6 if(A[mid]=mid)
7
You guys are working too hard. Think about the sequence of numbers
[ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this
sequence to find the number of zeros. If you think about it for a
while, you will see that this sequence is non-decreasing. It must be
a segment of zero or more
I should have mentioned that this problem only makes sense if the
array values must be unique.
On Dec 6, 8:20 pm, Gene gene.ress...@gmail.com wrote:
You guys are working too hard. Think about the sequence of numbers
[ A[i] - i | i = 0,1,2,...n-1 ]. You are trying to probe this
sequence to
If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
FIND_EQUAL(A,start,end)
1.Go to the middle element
2.If A[mid]==mid)
return mid+1;
if(A[mid]mid)
yaar I can use simple O(n) sweep to find out who all are equal, I think it
can't be less than this
On Sat, Dec 4, 2010 at 8:05 PM, Abioy Sun abioy@gmail.com wrote:
2010/12/4 ankit sablok ankit4...@gmail.com:
as all the elements are sorted in the array make a min heap of the
array
@Nikhil
run you algo ..
on test case
index - 1 2 3 4 5
value - 1 2 3 4 5
ouput is mid+1= 3+1=4
but it should be 5...
correct me if i am wrong... and u have assumed all are positive, hence base
index should be 1
On Sun, Dec 5, 2010 at 4:41 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote:
If
@ashim please refer my post.I posted an o(lgn) algo.i.e. I am copying again
below with an update
If All the elements are unique and sorted in ascending order then we can
design an algorithm for O(lgn) and all nos are positive.
Run FIND_EQUAL(A,0,N-1) [A0,A1 and A2 are the array elements]
2010/12/5 juver++ avpostni...@gmail.com:
Wrong.
Counterexample: 1 2 2 2 2 6
suppose you mean 1 3 3 3 3 6?
1) divide-conquer
2) search binary, in each sub array [s, t],
mid = (s+t)/2
if t array[mid]:
// no need to check the part after mid, all will fail
else if s array[mid]:
// no need
still there is some problem related to numbers encoding like..
22333101 here how will u going to
encode it???
On Tue, Sep 28, 2010 at 1:38 AM, ligerdave david.c...@gmail.com wrote:
it's a compression problem. using hex instead of oct saves more space
that will be
12 23 34 1 0 1c1
what's the some related problem?
only last char in the group represent the char, leading chars
represent the number of the repeated char. space(or whatever you like
it to be) is the separator of groups. when you see space, replace w/
'\t'.
On Sep 28, 2:58 am,
it's a compression problem. using hex instead of oct saves more space
00aaa0ss yyy = 50 2a 0 1s 3f 1\s ay
On Sep 15, 8:21 am, bittu shashank7andr...@gmail.com wrote:
A file is given with many 0s stored in continuous way , store it in
another file such that when you store try
These a reverse of binary search
1. iteration would be 1,2,4,8,16,32...
2. ex. array a has the infinity 0's . Let it be n(very
large)
count=1;
for(i=1;in; i=(2^count))
{if (a[i]==0)
b[count]=1;
Finding the longest increasing sub sequence and comparing with the
original array ...will this method work?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe
ya exactly..dp solution is working...
On Sep 5, 7:28 am, Gene gene.ress...@gmail.com wrote:
I just figured out you are running the first (incorrect) greedy
algorithm I tried. Please try the DP. It works fine.
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice
i think this prob cannot be solved by DP then...
Because anytime a new value coming into the non decreasing sub-array
obtained by the
DP equation can be disrupted(like in the above example).
I think a backtracking approach cud prove useful.
(Recursion)
anytime we get a new element we can do two
I just ran the code with your example and it produced 22.
Here is the C table:
m = 11 13 20 22
n = 1 : 9 7 0 0
n = 2 : 20 16 2 0
n = 3 : 22 16 15 13
n = 4 : 22 22 22 22
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice solution..
but it's not
I just figured out you are running the first (incorrect) greedy
algorithm I tried. Please try the DP. It works fine.
On Sep 3, 2:18 pm, Discover maniksinghal.n...@gmail.com wrote:
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should
@gene: nice solution..
but it's not working for a[]={20,22,13,11};
ur code will give soln : 24
but ans should be: 22 {11,11,11,11}
pls correct me if i m wrong
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09
nice explanation gene :)
On Sep 2, 8:35 am, Gene gene.ress...@gmail.com wrote:
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I
Okay. First, you can make the DP more efficient than the one I gave
earlier. You don't need to scan the whole previous column when
calculating costs of decrementing. Rather there are only two
possibilities.
I will add that rahul patil's solution looks correct, but it's
exponential time. DP is
I think your code is just the dynamic program for solving this.
Let V be the set of values in the sequence A[1..N].
Then define C(n, m) to be the minimum possible cost of making A[1..n]
into a new non-decreasing sequence B by decrementing and deleting
elements from A with the constraint that all
On Aug 29, 10:43 am, rahul patil rahul.deshmukhpa...@gmail.com
wrote:
Just read the comments. You will get logic.
1 read global variables
2 start with main
3 read rec (a recursive fn)
The main logic is that whether to keep the no in the final no (by
decrementing it)
or to completely
@gene ..if u just give an example herethat will make things more
clear...
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
check out this solution.I think this works correct
will explain logic if u find it correct.
#include stdio.h
#define SIZE 4
int result[SIZE];
int final_cost = 10;
int curr_ans[SIZE];
void save_arr(int *result)
{
int i;
for (i=0 ;iSIZE ;i++) {
curr_ans[i] = result[i];
}
}
void
@Rahul Patil:
I ran your code on some basic test cases and i found it to be
correct!
Can you please explain the logic you used to arrive at the solution?
Thanks :-)
On Aug 29, 12:25 pm, rahul patil rahul.deshmukhpa...@gmail.com
wrote:
check out this solution.I think this works correct
will
@ Gene:
Sorry I misunderstood the problem.
I thought the other operation is of increment rather than decrement... My
bad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
Just read the comments. You will get logic.
1 read global variables
2 start with main
3 read rec (a recursive fn)
The main logic is that whether to keep the no in the final no (by
decrementing it)
or to completely remove it.
#include stdio.h
#define SIZE 4
int result[SIZE];/*Array for
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas minimum cost will be : 8
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
I think this problem is a DP problem too.
Google Code Jam Round 1A has a similar problem in this year.
http://code.google.com/codejam/contest/dashboard?c=544101#s=p1
In the contest analysis page. It also explains the detail.
http://code.google.com/codejam/contest/dashboard?c=544101#s=aa=1
--
Yes. My solution isn't right. It's not a matroid, so greedy doesn't
work. You need a dynamic program.
On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote:
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas minimum cost will be : 8
My proposed solution was not correct. You need a DP because the
problem is not matroid as I thought.
But for this problem 14 seems correct to me. I can't see how you can
get 8. You need to decrement 14, 15, 16 and 13 to 11. This is a
total of 14 decrements. What am I missing?
On Aug 28,
Ouch. I think I was right to begin with and it is a matroid. I should
have been greedy right-to-left rather than left-to-right. This is
because you can only decrement. If we were incrementing instead, then
left-to-right would work fine.
So work right to left and for each item either
a)
My algorithm proposal wasn't correct, but I can't see how to get 8.
You need to decrement 14, 15, 16, 13 to 11. This costs 14.
On Aug 28, 5:41 am, gaurav singhal singhal08gau...@gmail.com wrote:
@ Gene :
Output for
int a[] = { 14, 15, 16, 13, 11, 18 };
is coming out to be 14
whereas
On Sun, Aug 29, 2010 at 1:35 AM, Gene gene.ress...@gmail.com wrote:
My algorithm proposal wasn't correct, but I can't see how to get 8.
You need to decrement 14, 15, 16, 13 to 11. This costs 14.
So do I.
May be he has not noticed that incrementing a number is not an option. ;)
On Aug 28,
@Rahul:
Yea that is admissible.. Each decrement will add one to the cost!
On Aug 27, 9:36 pm, Rahul Singal rahulsinga...@gmail.com wrote:
can u decrement d same element more then once ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
This code is giving incorrect answer in some inputs.If possible someone
correct it.
#includestdio.h
#includeconio.h
static int SIZE=5;
void print(int *array);
int del(int *array,int i);
int decrement(int *array,int i);
void print(int *array)
{
printf(\n);
int i=0;
Explain the logic also
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
greedy won't work on 8,2,2,2,2,2,2...
On Sat, Aug 28, 2010 at 7:39 AM, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into the
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09 am, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It looks like a trivial matroid, so a greedy
algorithm will work fine. The obvious greedy algorithm is to work
left-to-right and incorporate elements into
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your solution works like charm!
On Aug 28, 7:09 am, Gene gene.ress...@gmail.com wrote:
This is a nice problem. It
Ya it fails.. Should it then be Dynamic Programming then??
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot!
Should it be done using dynamic programming then?
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2 2.. is six..
On Aug 28, 8:26 am, jagadish jagadish1...@gmail.com wrote:
@Gene: Thanks alot! :-) your
Yes. Exactly. DP will get it.
On Aug 27, 11:34 pm, jagadish jagadish1...@gmail.com wrote:
Ya it fails.. Should it then be Dynamic Programming then??
On Aug 28, 8:32 am, jagadish jagadish1...@gmail.com wrote:
@Aravind: I think the solution given by Gene works!.
The answer for 8 2 2 2 2
@Gene:
It would be helpful if you could throw some light on the sub structure
of the problem!
And how to formulate it..
Thanks for your time :)
On Aug 28, 8:36 am, Gene gene.ress...@gmail.com wrote:
Yes. Exactly. DP will get it.
On Aug 27, 11:34 pm, jagadish jagadish1...@gmail.com wrote:
@harit..
logic plz.. not the code..
On Wed, Jul 14, 2010 at 9:50 PM, harit agarwal agarwalha...@gmail.comwrote:
this is O(n) solution and using O(n) space...
#includeiostream
#includevector
#includestack
using namespace std;
void leader_count(vectorint v,int *ar)
{
stackint s;
int
One approach will be while creating a BST and also store position of the
element in the original array. While constructing ar_low check for two
condition 1. element should be less than the given element and also position
of element should greater than the given element.
On Tue, Jul 13, 2010 at
I guess it is a dynamic programming problem.
On Wed, Jul 14, 2010 at 11:34 AM, Anand anandut2...@gmail.com wrote:
One approach will be while creating a BST and also store position of the
element in the original array. While constructing ar_low check for two
condition 1. element should be less
It is counting the inversion counts
use merge sort and count the inversions for each element
O(nlogn) time and O(n) space
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To
this is O(n) solution and using O(n) space...
#includeiostream
#includevector
#includestack
using namespace std;
void leader_count(vectorint v,int *ar)
{
stackint s;
int n=v.size();
int i=n-1;
while(i=0)
{
if(s.empty())
{
ar[--n]=0;
s.push(i);
i--;
}
else
{
if(v[i] = v[s.top()])
{
Initialise all elements of ar_low with 0
for (int i=0; in-1; i++) {
for (int j=i+1; jn-1; j++) {
if (ar[j] = ar[i])
ar_low[i]++ ;
}
}
O(n^2)
For O(nlogn), create a BST - O(nlogn)
Traverse the tree, counting children on the left side of each node and
putting it
actually the problem is to make BST construction in O(nlogn)...
we need rotations which changes the structure so you wont be able to
distinguish between elements right to a particular elements, elements left
to it . ( in original array )..
On Tue, Jul 13, 2010 at 12:52 AM, Tech Id
make a balanced bst which also has the size of subtree at each node
start from ar[n-1] and insert each element and see what is it's rank in BST
for finding the rank when inserting each time you pick the right subtree add
size of left subtree to rank
O(nlogn)
--
You received this message because
// sort ar[]
and store in temp[] -- o(nlogn)
for(i=0 to n-1)
{
//search position of ar[i] in temp[] binary search --o(logn)
ar_low[i] = pos-1;
delete temp[pos];
}
in binary search increase pos until next element is same .
On Tue, Jul 13, 2010 at 4:09 PM, Amir
101 - 199 of 199 matches
Mail list logo
