@ all.
what if we use greedy approch..like if we slice when in remaining fruits on
screen any one fruit is going to disappear?will it work?
On Friday, February 1, 2013 9:07:14 AM UTC+5:30, emmy wrote:
Ohk.. I finally got it.
Thanks guys!!
This was great help.
On Mon, Jan 28, 2013 at
on first iteration *ptr == 'h' so it will enter in the loop.
ptr++ -- *ptr == 'e';
comparing *ptr with least i.e 127 (ascii) *ptr will be 'e' now;
2nd iteration *ptr == e
ptr++ - *ptr = 'l'
comparing 'e' with 'l' and 'e' will be assgined to least and so on;
coz 'e' has the
two arrays are suppose x[n], y[n];
take a function
f( x(i, n), y(j, n) , 0) -- taking x[i] as a first element of merged array
then max sum;
f( x(i, n), y(j, n), 1) -- taking y[j] as a first element of merged array
then max sum;
f( x(i, n), y(j, n) ,0) = max( { x[i] * x[i+1] + f( x(i+1, n),
@sanjay it's not like that
e.g : (3 5 6 7 8 4) 7
1 2 3 4 5 1 2
Yes we have to increase just by one, but while decreasing choose the lowest
possible such that each trivial component, if it is in decreasing phase,
should end with 1.
On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey
order in mind.
On Sat, Jul 7, 2012 at 5:23 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
i was thinking of character array. which is same as string.
Any thoughts on better alternatives?
On Friday, 6 July 2012 13:34:01 UTC-4, anshu wrote:
yes, We can have much better data structure
differs? or is there any other reason?
-mithun
On Fri, Jul 6, 2012 at 12:58 AM, payal gupta gpt.pa...@gmail.com wrote:
thnx...4 d rply..
Regards,
PAYAL GUPTA,
NIT-B.
On Fri, Jul 6, 2012 at 12:43 AM, Anshu Mishra
anshumishra6...@gmail.comwrote:
First define all the basic operation
First define all the basic operation you can apply on two numbers.
Binary operation : +, -, *, /, %, optional((and), |(or), ^(xor))
Unary operation : !, ~, -
Comparison : , ==, !=
Define all these operation.
Most simplest one can be,
class BIG_INT {
private string val;
//Define
awesome question :D :D
--
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,
first try to understand the sol then comment. it is for binary tree not for
BST.
On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
For BST it would be rather simpler. find the first node which lies in
between the two.
On Wed, Nov 16, 2011 at 1:44 PM, anshu
Node *LCA(node *root, node *e1, node *e2, int x)
{
Node *temp =NULL;
Int y = 0;
If (root-left) temp = LCA(root-left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
index = 0 1 2 3 4 5 6
ar = 0 1 2 -4 -3 6 -3
sumar = 0 1 3 -1 -4 2 -1
first index where we get the number which has already appeared in sumar will
be the last index of sub array whose sum will be zero and (index of first
apperance of this number + 1) in sumar will be the start index.
@Ravindra
To check the particular number square can be written as sum of two squares
or not.
If it has any prime factor x such that x % 4 == 1 then only.
Now about time complexity.
suppose u have given array is.
10 6 13 9 17 4 18 12 1 5.
now u can easily skip the numbers(1, 4, 6, 9, 12, 18);
this is an O(n^2) solution. By pre processing the array we can also solve it
O(n)
int find_mid(int ar[], int s, int e, int val)
{
int i;
for (i = s; ar[i] val; i++);
return i;
}
node * constructTree(int ar[], int s, int e)
{
node *root;
root = new node();
root-val =
@Anand
As given it is a BST so any single traversal(pre or post or in) is
sufficient to construct the tree. :P
--
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
@Ravindra
may be the interviewer wants from u that instead of blindly checking for
every number. first check that particular number can be written as the sum
of two squares or not if yes than only search for that number. So the order
will be decrease from O(n^2) to O(n * (number of side which is
If O(k*logk) solution is acceptable then it is very simple.
maintain a min heap.
push a[0][0],
i = 0;
while ( i k)
{
pop an element. --- O(log(i)) -- coz number of elements in heap is i;
push the two adjacent element that is one right and right below. ---
O(log(i));
i++;
}
last element popped
push the two adjacent element that is one right and below
--
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
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
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
@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19 that will repeat.
but it in
string all1Multiple(int x)
{
string s;
setint mySet;
mySet.push(0);
int psize, r=1;
do
{
psize = mySet.size();
s += '1';
r = r % x;
mySet.push(r);
r = r * 10 + 1;
} while(mySet.size() psize);
if (r != 1) return not Possible;
return s;
}
--
You received this message because you are subscribed
the simplest code could be for this question is
void printAllSubsetSum(int ar[], int n, int x)
{
for (i = 0; i (1n); i++)
{
int sum = 0;
for (j = 0; j n; j++)
{
if ( (1 j) i) sum += ar[j];
}
if (sum == x)
{
wat is ur question finding maximum path sum or anything other than this?
--
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
do this way.
start with any node(k) calculate sk = sum(k, i) for all i 0 = i n;
and u can easily get sj = sum(j,i) where j is adjacent to k; in O(n);
suppose nj = number of nodes remains after removing edge(j,k) in subtree
containing node j;
suppose nk = number of nodes remains after removing
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}
main()
{
for(i=n-1;i=0; i--)
{
sol[i] = insert(ar[i], tree, 0,
In which year you are now. May i can give you some idea.
--
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
use segment tree or binary index tree to solve O(nlogn)
--
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
node* LCA(node *root, node *n1, node *n2, int x)
{
int y = 0;
node *temp;
if (root-left) temp = LCA(root-left, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return node;
if (root-right) temp = LCA(root-right, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return
*@all to median of BST time O(n) space O(1) (modified code of nitin to
get median)
medianBST*(node, n)
int x = 0;
*while* hasleftchild(node) *do*
node = node.left
*do*
x++;
if (x == n/2) return node-val;
*if* (hasrightchild(node)) *then*
node = node.right
You cant do.
--
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
do the inorder traversal as soon as reached at n/2th element that will be
median.
--
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
int bstMedian(node *root, int n, int x)
{
if (node-left) return bstMedian(root-left, n, x);
x++;
if (x == n/2) return node-val;
if (node-right) return bstMedian(root-right, n, x);
}
call bstMedian(root, n, 0);
--
You received this message because you are subscribed to the Google
its not o(n) it is O(max height of tree) :P
i have not seen the constraint.
--
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
suppose adress of a = 0x12;
0x12 has
0x13 has 0001
so p = 0x12;
p++ = 0x13;
now modifying the value pointed p by will modify the only 0x13 bcoz it is
char type pointer and its value wiil be 0010
so finally 0x12 to 0x15 will have 512
--
You received this message because you are
If we know the size of heap we can get the minimum element in O(n);
int findMinFromMaxHeap(int ar[], int n)
{
if ( (n+1) n == 0)
{
for (i = n1; i n; i++)
min = min ar[i] ? ar[i] : min;
}
else
{
int x = n, y = 1;
explanation:
Node :
lock - that node is locked or not;
lockedDesc - number of descendents locked of that node
left, right,par as name sugest;
unLock():
when we unlock a node than all its ancestor has to decrease its lockedDesc
value by 1.
Lock():
when we lock a node than all its ancestor has to
as function object also
--
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,
you can use mergesort technique, segment tree, binary index tree or BST
--
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
for simplicity i doing it for binary tree
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;
while (temp != NULL)
{
for simplicity i am doing it for binary tree (liittle modification)
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;
void allCase(string r)
{
int n = s.sise();
string s;
for (i = 0; i (1 n); i++)
{
s = r;
for ( j = 0; j n; j++)
{
if ( i ( 1 j) )
{
s[j] = s[j] + ('a' - 'A');
}
}
http://www.spoj.pl/problems/AIBOHP/
same problem u have asked!!
--
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
How you got the call buddy
On Aug 10, 11:43 pm, vishwan baghla vishwanbag...@gmail.com wrote:
--
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,
For those people who want to get rid of sohail panzer spam
create a filter
From : sohail.panz...@gmail.com
mark on Delete it
--
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
@ akash
solution is complete. :P
first try to understand the solution.
--
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
@ross no, a particular element has to read only 5 times maximum.
1 reading (i,j) (if its flag is already false skip)
2 read by top element
3. read by bottom element
4 read by left element
5 read by right element
coz atleast one of the this operation its flag will be unset(false), then we
have to
biaprtie graph is special case when we can color the whole graph just by
two colors.
--
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
main()
{
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already
this is a very standard problem :D
start with any node(x) find the node which is at maximum distance.
now start with x travese the tree and find the node(y) which is at maximum
distance.
so finally answer wil be (x, y)
traversing the tree two times. so the order for finiding the such nodes
little modification
start with any node(r) find the node(x) which is at maximum distance.
--
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
it is exactly a graph coloring problem. so it has no polynomial order
solution.
--
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
write these three lines in ur function, it will bind that particular thread
to (id)th processor wher
void func(int id)
{
unsigned long mask;
mask = 1id;
pthread_setaffinity_np(pthread_self(), sizeof(mask), mask);
}
main()
{
pthread_t *thread;
thread =
PS dont forget to bind ith thread with ith processor
--
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
it is a simple graph problem. travese the whole matrix using BFS. it will be
O(n^2).
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
--
You received this
@vishal ur sol wil give wrong answer for this
1 1 2
1 3 1
2 3 4
answer should be 6 but ur sol wil give 4.
--
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
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
You received this message because
map is internally implemented with balanced binary tree and inserting in a
BST is o(logn);
--
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
@all go through this code
#includeiostream
#includealgorithm
using namespace std;
bool compare(int a, int b)
{
string u, v;
u = v = ;
while (a)
{
u += (a % 10 + '0');
a/=10;
}
while (b)
{
v +=
it is os responsibility to map user level thread to kernel level thread.
Usually os implements many to many mapping.
In pthread we can bind a particular thread to particular processor or set of
processor.
--
You received this message because you are subscribed to the Google Groups
Algorithm
@gopi
by mistake i have written i in place of IN[i];
my fault, 2nd thing( (F[i].idx - F[i-1].idx - (F[i].rep - F[i-1].rep) ) i
have really not think of that. thanks :)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
first for every element get the number of element before its index have less
value.
example
L[]= 0 0 1 1 3
D[] = 8 1 3 3 8
IN[] = 0 1 2 3 4
you can use segment tree for this it will give solution in o(nlogn);
after that sort the array and start from 0th index
D[] = {1 3 3 8 8}
two thing i have forgot do;
that is at every iteration
rem--;
last = D[i-1];
--
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
L[i] tells how many elements D[j] less than D[i] such that j i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));
rem = n;
curtime = 0;
last = 0;
for (i = 0; i n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i
@sravanreddy001
u r not at plain surface its sphere :P :D. u have to go by angle
--
Anshuman Mishra
IIIT Allahabad
-
anshumishra6...@gmail.com
rit2007...@iiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
@sravanreddy001
no u will go from point A to point B by walking on the surface not by making
the tunnel in the earth.
--
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
@piyush
suppose A is latitude
nd B is longitude, R is raduis of earth
z = Rsin(A);
r' = Rcos(A); radius of circle at z height;
x = r'cos(B);
y = r'sin(B);
(x,y,z) is coordinate of point assuming (0,0,0) is the center of earth;
--
You received this message because you are
@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
for 12 answer will be 36? is it ur question?
--
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
the same question i have asked in microsoft interview. (if it is the same
:P)
for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
i have given them 3 solution(recusrsive, stack based) and the last one what
they wanted.
take a tertiary number(n) = 3^(number of digits) in case of 12 it is
@sravanreddy001
suppose u have to calulate A^n u can calculate in O(d^3*log(n));
d is dimesion of matrixl
while (n)
{
if (n1) mul(ans, A, d);
mul(A, A, d);
n =1;
}
--
Anshuman Mishra
IIIT Allahabad
-
its DP problem can be solved in O(m*n)
where m is number of elements in array and n is value of the given number.
--
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
we can use BIT or segment trees.
algorithm using segment tree
1. intialize all node wid zeros
2. read the array element according their index update the node value.
void update(int s, int e, int k, int node)
{
if (tree[node] ar[k]) tree[node] = ar[k];
if (s==e) return;
mid = (s+e) 1;
if (k =
void query(int w, int s, int e, int node)
{
if (s==e)
{
tree[node] -= w;
prpogateNewMax(node);
return;
}
mid = (s+e)1;
if (tree[(node1)+1] = w) query(w, s, mid, (node1)+1);
else query(w, mid+1, e, (node1)+2);
}
void prpogateNewMax(int node)
{
if (node == 0) return;
int par = (node-1)1;
int a =
@amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};
--
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
no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 -- 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its
explain your logic instead of posting code, use binary index tree or segment
tree or bst to solve this problem.
--
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
@pacific you are perfectly right but the order is not o(kn) its is
O(k*n*log(n)) because to get the least number u have to use priority queue
nd at every iteration (from 1 to k*n) u have to push and pop one single
element.
--
Anshuman Mishra
IIIT Allahabad
-
@gaurav both things are same, matrix is a simple and efficient way to
do problem like this.
.
--
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,
@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};
f(i, j) = f(i-1, j-ar[i]) + 1 -- if (i-1, j-ar[i]) != -1;
answer will be the largest j for which f(i, j) will be exactly equals to
n/2;
there is something more in this but when
Use KnapSack DP. suppose the sum of element = s and number of elements
= n make a 2-dimesnsional array of size n * ((s+1)/2); I think that
much hint is enough.
if we think little bit more we can optimize it also.
--
You received this message because you are subscribed to the Google Groups
algorithm:
if any number(a) is divisible by 5 it can be wriiten as 4*b + b --
this cleary shows the last two bit of a b will be same.
lets understand by an example (35)10 = (100011)2
xx1100
+ xx11
-
100011
now this clearly shows we can calculate the unknowns(x) by traversing
right
yeah..Sorry for the mistake ..
I did not check boundary conditions correctly..
your correction should make it work perfectly..
We can also add a little optimization to not push the last one ..
because as soon as its pushed its popped..
Thanks,
-anshu
Thanks,
-anshu
On Sep 9, 8:33 am, chandra
meke a corresponding cumulative sums array..
where S[i]= Summation(a[0] ... a[i])
Sum of subseq. [i..j]= S[j]-S[i-1]
check all i,j pairs
but this is O(n^2).. may be a better exists
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
82 matches
Mail list logo