I THINK...
D 10
C 10
B 10
A 20
SORRY I AM NOT SURE WITH THIS.
On Fri, Dec 7, 2012 at 4:12 PM, zerobyzero narayan.shiv...@gmail.comwrote:
what will be the size of union A ,B,C and D. also please explain the logic.
* union A{*
* long int y[5];*
* union B{*
*
Let me give an example.
For 17 next multiple of number 5 is 20.
For 20 next multiple of number 5 is 25.
And give solution for this proeblem also:
For 17 next nearest multiple of number 5 is 20.
For 20 next nearest multiple of number 5 is 20.
*VIHARRI P L
@aditya : I am wondering how many times 7 has occurred. Is it 1? Or is
it 0?
Please take a moment before posting your solution, and think whether
it is write or wrong!
On Jul 6, 12:11 am, aditya kumar aditya.kumar130...@gmail.com wrote:
Q3. ans:7000 i guess this is also a correct answer and
There is one way in which we can do O(n).
Convert the numbers in base 'n'. [ O(n) ].
Now, there are 2-digit numbers, each digit ranging from 0 to n-1.
You can call count-sort 2 times (for each digit), so, complexity is O(n
+n) =O(n).
On Jun 27, 12:22 am, Dan dant...@aol.com wrote:
Your question
This happens because 'd' is automatically cast into type 'size_t'
which is basically unsigned int type.
So, it compares with TOTAL_ELEMENTS. Explicitly cast it into
int, if you want it to work!
On Jun 25, 3:23 pm, harshit pahuja hpahuja.mn...@gmail.com wrote:
#includestdio.h
#define
The answer fits in 64 bit range.
The calculations done are of the form D = (A*B) / C. Here {A,B,C,D}
can be represented are 64 bit integers.
But we cannot say that A*B will be a 64 bit integer and will cause
overflows.
To avoid this,
Let's say G=GCD(A,C). Then the above can be written as D =
The ordering of coins matter for this problem.
For ex.
1 2 and 2 1 have different results.
So, i don't think that there would be a direct formula for this
problem.
We will have to traverse all the heaps of coins determining whether
the current player is in winning or losing position.
On Jun 15,
Sorry, i confused val with weight of the edge.
BFS would be a better option.
On Jun 14, 5:31 pm, L prnk.bhatna...@gmail.com wrote:
Any graph algorithm would work.
If val is positive then use Dijkstra's algorithm, otherwise use
Bellman Ford.
On Jun 14, 5:07 pm, Raghavan its...@gmail.com wrote
Any graph algorithm would work.
If val is positive then use Dijkstra's algorithm, otherwise use
Bellman Ford.
On Jun 14, 5:07 pm, Raghavan its...@gmail.com wrote:
Hi,
How to find the shortest path in a 4-ary tree in an optimal way?
Node tree{
Node *left,*right,*top,*bottom;
int val;
};
Use ternary search to find the minimum number. (In this case 1)
Then you have two sorted arrays, one ascending and one descending.
Now, you can apply binary search. First, check the number with the
last element and the first element and chose the appropriate array for
searching.
Time complexity:
Ah! sorry.
This combination is not possible.
It will be 10,10,10,10,10,4,2,0. So, the answer is 11.
On May 27, 10:10 pm, L prnk.bhatna...@gmail.com wrote:
The worst case will occur when 5 teams have the same number of wins.
As only 4 can qualify, one team with the same number of points
linus.prob...@gmail.comwrote:
If the numbers are unique you could use a bitmap-sort this way you could
easily read just parts of the file at a time.
If they aren't unique it gets a bit trickier.
/L
dinesh bansal wrote:
Hi All,
Suppose I have a big file (~100M) containing integer data. I want
Hi,
Although, I cannot give you a complete solution right now..I will give you
the following relations (I am not sure If they are correct.discussions
welcome)
T(0, x) = 1
T(x, 0) = 1
T(1, x) = (x+1)
T(x, 1) = (x+1)
T(n, m) = Sum[i=0..n] { T(n-i, m-2) * (i+1) }
If you are looking for a
Hi,
I guess he is going by the assumption that the queries will be large
enough that precomputing the all-pairs shortest paths is better.
Anyways..mukesh..this is what you need..
In the place of your output
while(cin.get(c) c!='\n')
{
cin.unget();
I guess it was a slight difference in terminology...you must have then
phrased the question as almost complete rather than a complete tree since
you are allowing the last level to be incomplete.
Anyways, If the last level is going to be incomplete, then the observe
this..
sum of the nodes is
Read the post again...
The adversary then chooses the split up, that is, the part of the
string you've given him that loop
you can only choose the string 'w' (=n), the adversary can only _CHOOSE X,
Y and Z_ but ofcourse the adversary is restricted by the fact that he had
chosen a 'n' earlier and
DFS
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more
well...its simple as given in the article..
note that the numbers are all decimal numbers (not binary..in case
misled by just 0 and 1 in the number) therefore
if you have have k copies of 001 and k%3 == 0, then the sum of the
digits is divisible by 3 hence the number is divisible by 3 - The
In case you are wondering about the part of the proof for k%30, it
goes like this, the given number can be written as 1 + 1000 + 100
+ 10 +..and so on
now if for a given k, if we choose the string of k 1s and try to find
the modulus with each of the terms in the above expression,
for
Oooh...I almost forgot to add this..
notice the relation between the proof for part (ii) and the discrete
logarithm problem. The proof is no mere coincidence. This is the reason
behind using primes in encryption schemes that rely on the hardness of the
discrete logarithm problem. This will ensure
Now in the case of non complete BSTs it may run into trouble...I never
handled them. It will work for complete BSTs though as it is. Refer to
a previous thread in algogeeks where i had posted the thread inplace
sorting and look at the solution by atamurad for the explanation.
Well... I think a hash function is chosen only once for each run of
the program and not for each time a value is hashed. Thereby you dont
have such issues at all.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
sorry
RR* = R+ is the valid assumption
--~--~-~--~~~---~--~~
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
Yes...the proof is correct and this is what stone had suggested in his
earlier post.
Consider one red sector in the inner disk in each of the 200
different positions, it will match against exactly 100 sectors in the
outer disk since there are 100 of the red sectors in the outer disk.
Similarly
An unique BST does exist for such an array if you assume the root to
be 1, then automatically you will be able to fix the left and right
children of the root and so on.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
@alfredo:
I dint get this part:
1) Lets say that we have the outer circle painted in the following
manner: 1 red(C1), 1 white(C2), 1 red(C3), etc. We call this sections
(RWR)
2) Then if we have that the inner circle is painted in the same way we
finish.
3) if not then lets say that we have a
#includestdio.h
#includestdlib.h
#includemath.h
#includestring.h
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
yes...but you can sort without constant space using the posted algorithm
--~--~-~--~~~---~--~~
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
yes...but that does not mean that you can assume that the 100 reds and
100 whites are contiguous blocks.It just says that the outer disk has
a sum of the 100 reds and 100 whites and does not say that they are
contiguous.
--~--~-~--~~~---~--~~
You received this
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and
i am sorry that is a[i] = ++cnt
I made a mistake when pasting the code...
--~--~-~--~~~---~--~~
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
The standard link
http://graphics.stanford.edu/~seander/bithacks.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
Find the longest common prefix in the path from the root to nodes u and v
--~--~-~--~~~---~--~~
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
A DFA is possible I guess which is interesting, see if the following
DFA works, since the existence of the DFA relates to the existence of
a Regular Expression Describing the language
State/Input 01
q00 q10 q01
q10 q20
If the DFA works then it can be converted to a regular expression
using standard techniques like the one described in
http://www.cs.colostate.edu/~whitley/CS301/L3.pdf
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
To make things more easier just assume a complete binary search tree
--~--~-~--~~~---~--~~
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
the LP:
v1 = 40
v2 = 30
v3 = 20
v1 + v2 + v3 = 60
v1*2 + v2*1 + v3*3 = 100
Maximize: v1*1000 + v2*1200 + v3*12000
Here v1, v2 and v3 are the volumes of the materials 1, 2 and 3 to be taken.
--~--~-~--~~~---~--~~
You received this message because you are
The question is not to print out a sorted array which we can easily do
by inorder traversal. The question is to store the sorted array in the
same array with constant extra space.
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
I agree with you completely but for the problem that I posted it is
enough that we have O(n) in accessing the elements in order. Your
solution does better by calculating every element in O(1) time. The
key now is to do the actual sorting with this method
Another variant...(or rather wanted to say in my previous post)
How do you find a maximum square of all ones in a binary matrix of 0s and
1s?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
I give a try to start at an O(mn) algorithm (where m is the size of the
longest bar)
Maxrect[height][width] =
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email
A shot at an O(nlgn) algorithm.
Do a sweep line from top to bottom. Only look at the events when a new bar
is introduced (this is accomplished by sorting the bars based on height).
When a new bar arises, if there exist values immediately to the left and
right of the bar just merge them into a
yes..thats the reasoning that i had too but let us see if anyone else sees
some thing fishy in our reasoning
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
why is it 1 - (area of triangle)/(area of Sq.)?
why do we need a square since what would happen is that the 4th point can be
anywhere in the space but the area of the triangle is bounded. The
probability of choosing a point outside the triangle would be 1 (bound - not
exact by reasoning as in
On 2/14/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Hello,
There is a problem in the algorithm book I'm trying to digest, that
I'd like to discuss a bit. So, first thing first, let me state the
problem :
find(A, x)
sort(A)
i = 1
j = n
while (A[i]+A[j] != x)
{
It does depend on the size of the problem you have in mind. Tries can be
expensive for names depending on the sparseness of the data set, you may
waste a lot of pointers. If you use B-Trees they may be good in such cases.
B-trees are generally a bit better when it comes to data stored in a disk
permutation (List resultSoFar, List remainingElements)
{
if(length(remainingElements)=0)
return;
for i = 1 to length(remainingElements)
{
print resultSoFar+remainingElements[i];
permutation (resultSoFar+remainingElements[i],
remainingElements-remainingElements[i]);
yes..i agree with rajiv..you seem to be generating combinations rather
than permutations..the algo that i have given generates permutations
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
Split the marbles into sets of 4 each
Compare the first and second sets
If both the sets are equal (the problem is in third set)
{
choose 2 of the marbles in the third set
compare with 2 marbles from the first set(which we know are good)
if comparision is equal
{
compare one of
Hi,
You can try a similar technique...
Start at an arbitrary endpoint,
Set the number of open chords to zero,
Set the number of intersections to zero
Traverse the endpoints along the circle in one direction (made
possible by sorting radially)
{
If the endpoint is one that closes
You could use a B-Tree or even a simple binary tree to index into the
array, but the space will be doubled (it is justified if you store
some other object in the array other than integers).
On 11/17/06, Nik [EMAIL PROTECTED] wrote:
Hi,
I have an array in which elements are present .
The
-- Forwarded message --
From: Karthik Singaram L [EMAIL PROTECTED]
Date: Nov 12, 2006 4:58 PM
Subject: Graph Partitioning
To: algogeeks@googlegroups.com
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph
I am not sure but an arbit way to do this would be to find
(totalsum/k) and do a bin packing for each of these , of course we
would be left with a few elements, we can put them in the bins with
max.slack space...It would be approximately correct I guess though not
sure.
Hope it helps
karthik
On
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph whose nodes are bit vectors of length n (the graph
contains all 2^n nodes), the edges are defined to be connecting all
the pairs of nodes which differ only at one bit
I am not sure If I got the question right
1
4
0 3 1 2 3
1 1 0
2 2 0 3
3 2 0 2
1 2
Isn't the answer that camarade 1 talks to camarade 0 who inturn talks
to 2. Isnt this shortest path algorithm? isnt Djikstra O(VlogV) which
seems feasible for the problem rite?
On 10/30/06, Pradeep
/* Assume inp is the given array*/static int bitmap[N][N];int lengths[N];int currentBitmap = -1;int active = 1;int lastPos;for(i=0;iN;i++){ if(inp[i]==1) { currentBitmap++;
active=1; lastPos=i; } if(active==1) { if(bitmap[currentBitmap][inp[i]]==1) { active=0; lengths[currentBitmap]=(i-pos); }
Let us say we call the following with the roots of both the treesalgo: checkIsomorphism (node1, node2){ if(node1==NULL node2==NULL) return 1; if(node1==NULL) return 0; if(node2==NULL) return 0;
child11=node1-left; child12=node1-right; child21=node2-left; child22=node2-right;
Hmmm.. Interesting
Just in case someone does want to use BFS and does not really care
about the time complexity,
then you could do BFS to get all the Paths ( do not remove them as
soon as you get them )
For example in the graph in the previous discussion, BFS would give
S37F, S345F and
of course the time complexity could be substantially reduced using the
flow model of the problem.l\
On 4/26/06, Karthik Singaram L [EMAIL PROTECTED] wrote:
Hmmm.. Interesting
Just in case someone does want to use BFS and does not really care
about the time complexity,
then you could do BFS
Try this variation
In the previous algorithm if i am correct the complexity is O(n), that
itself shows that an important step is missing somewhere. well this is
my guess about the algorithm. check if it works. I do not think this
is exactly the standard Bentley-Ottmann
Algorithm
The precondition
This is the problem of dividing a set into two such that the sum of their differences is minimum.This can be solved using dynamic programming as follows:
algo:
1. Create an array of size L say Arr[L] and initialize to zeroes
2. Put Arr[0]=1
3. For each program Pi
Scan the array Arr from the right
Exactly correct!!!
But for the proof and solution to be complete, we need to analyze this
for 7 the answer you have is dp[3]=3*dp[2]+1=3*[4]+1
Now can you see that for dp[2], the number of steps would be
000
010
011
That would be only 3 steps so dp[2] is only 3 . Am i correct?
Regards
karthik
I solved this problem ( A very very interesting DP solution I guess )The key to the solution is First try to Prove that the last bit can be set using only 15 onesand you will get the solution.Keep thinking!!!
( A clue :- use Mathematical Induction for the Proof and the DP follows)-karthik
63 matches
Mail list logo
