Re: [algogeeks] Doubt in removing loop from linked list
@ rahul sharma: the linked list is a combination of a list a-b-...-p-q and a cycle q-r-...-z-q. (z != p). noting that the start of cycle q is the only node with 2 predecessor: p and z. if 2 pointers meet at some node x, different from q, in last step they must have met at x', the predecessor of x. the above logic holds for all nodes in cycle except q. @ sanjiv yadav: They will meet at the start of loop. ex. a-b-c-d-e-c-d-e... First round: A: a-b-c-d B: a-c-e-d meet at d. Second round: A: a-b-c B: d-e-c meet at c. On 2012-3-9 18:39, sanjiv yadav wrote: No They will not meet at the start in a case containing 5 nods and having loop at the third node. once check this On Fri, Mar 9, 2012 at 3:48 PM, rahul sharma rahul23111...@gmail.com mailto:rahul23111...@gmail.com wrote: i have 2 pointers fast and slow.now if tehy meet there is a loop... now keep one ptr at meeting point and take other one to the begining of listmove both at speed of one..they will meet at start of loophow this happens???why they meet at start..plz tell logic behind this???thnx in advance -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Sanjiv Yadav MobNo.- 8050142693 Email Id- sanjiv2009...@gmail.com mailto:sanjiv2009...@gmail.com -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: How many ways n points can be connected
@rspr: Are you talking about dependencies in my approach? or adding new constraints? In my DP approach, f(n,m) only depends on f(n-1,m'), f(n-2, m') ,..., f(1,m') (m' = m) Using s(n,m) denoting the number of all graphs of n vertices and m edges, obviously s(n,m) = C(n(n-1)/2, m) Instead of counting connected graphs f(n,m), I count the number of the disconnected graphs g(n,m) = s(n,m)-f(n,m) 1. choose the n' (n'n) points in the first connected component (containing 1st vertex): C(n-1, n'-1) 2. count the number of ways to connect those n' vertices with m' (m'=m) edges: f(n',m') 3. count the number of ways to place the rest (m-m') edges among the reset (n-n') vertices: s(n-n', m-m') Total number of disconnected graphs of this type is: C(n-1, n'-1) * f(n',m') * s(n-n', m-m') Sum it over all (n',m') (n'n, m'=m), we get g(n,m), then f(n,m) = s(n,m)-g(n,m) On 2012-2-9 16:52, rspr wrote: @Terence: The DP approach is nice. if we have constraint likewhile choosing the first 3 edges if it makes a triangle so we will require n edges to connect the graph completely...in the same fashion...after selecting 2 more edgesagain we have to check that is it making more trianglethen no. of total edges will increase by 1 and now we will require total n+1 edges. So in such a scenario how we can compute the sample space for every cases. so for all the all the valid m what should be the sample space for f(n,m). if M(m1,m2,...) is all the vaild m. Then how we can calcualte the dependency between sample space for f(n,m1) and f(n,m2). @Terence On Feb 9, 8:22 am, Terencetechnic@gmail.com wrote: Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr- Hide quoted text - - Show quoted text - -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How many ways n points can be connected
Here is an DP solution: (consider only simple graph, with at most 1 line between any 2 distinct points, and no point connect to itself) Suppose f(n,m) is the number of ways m lines can connect n points. Then f(n,m) = 0 when m n-1 or m n(n-1)/2; For graph with n vertices and m edges (connected or disconnected), the overall count is C(n*(n-1)/2, m). There are 2 types: 1) connected: The number is f(n,m) that to be computed. 2) disconnected: Consider the connected component containing vertex 1, suppose it has n' vertices and m' edges. Then: a. there are C(n-1, n'-1) ways to select the points in the component b. there f(n',m') ways to connect the n' points using m' edges c. the rest n-n' vertices and m-m' edges can be arbitrarily placed. In summary, f(n,m) = C(n*(n-1)/2, m) - ∑(∑C(n-1, n'-1) * f(n', m') * C((n-n')*(n-n'-1)/2, m-m') for m' in [n'-1,m]) for n' in [1, n-1] (C(N, K) is binomial coefficient choosing K from N) The overall time complexity is O(m^2*n^2), and space complexity is O(mn) On 2012-2-8 12:03, rspr wrote: Hi All, can there be a formulato which we can estimate how many ways (n-1) lines can connect n points in the same way how many ways n lines can connect n points and so onthere is one way that we store the information in adjacency list or in adjacency matrixand will check for the same for every event in sample space.is there any other way that can optimize this calculation or may it possible that we can directly calculate it. . rspr -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
1. the computing of d is incorrect.
d = n-1;
while((d1)==0) d=1;
2. the accuracy of pow is far from enough. you should implement your own
pow-modulo-n method.
3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
need to implement your own multiply method in this case.
On 2012-1-18 18:15, Sourabh Singh wrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#includeiostream
#includeconio.h
#includemath.h
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int s,d;
for(s=0;1sn;++s); s--;d=(n%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
printf(x is %llu\n,x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k100;k++)
{
printf(%d is %d\n,k,is_prime(k));
}
getch();
}
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
@Sourabh
m=2^s***d
primes[i]**n
On 2012-1-18 19:39, Sourabh Singh wrote:
@Terrence
sry i didn't explain what s,d were they were also wrong i ws
calculating for n not n-1
earlier n=2^s+d
nw m=n-1; for odd n
m=2^s+d;
//suggested corrections made.. still not working..
#includeiostream
#includeconio.h
#includemath.h
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int m=n-1;
int s,d;
for(s=0;1sm;++s); s--;d=(m%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{if(primes[i]n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k20;k++) printf(%d is %d\n,k,is_prime(k)); getch();}
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ sunny agrawal
you are right. but i have used check an also . no improvement .
i think algo is wrong in later part.. somewhere..
@ Terence
1) pow may not work for big n but , m just checking for n=1..200
just to check wether algo is right.. and it's not working even for
n=7,19...
2) d,s are also coming fine for small values.. of n
3) for x i have used... 64bit integer.. uint64_t in it's declaration.
i just want to get algo right first then bother about big n ;-)
On 1/18/12, Terencetechnic@gmail.com wrote:
1. the computing of d is incorrect.
d = n-1;
while((d1)==0) d=1;
2. the accuracy of pow is far from enough. you should implement your own
pow-modulo-n method.
3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
need to implement your own multiply method in this case.
On 2012-1-18 18:15, Sourabh Singh wrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#includeiostream
#includeconio.h
#includemath.h
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int s,d;
for(s=0;1sn;++s); s--;d=(n%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
printf(x is %llu\n,x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k100;k++)
{
printf(%d is %d\n,k,is_prime(k));
}
getch();
}
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
error in pow.
as long as n 2^31, x*x fits into int64_t, since xn.
On 2012-1-18 20:51, Sourabh Singh wrote:
@ Terence
I belive nw its giving wrong answer for n41 onwards
due to error's in pow and x*x over flow as u already stated...
i guess algo is right nw.. ;-)
thanx again..
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ thanx got it.. silly mistakes ;-) . missed thought it ws + between s and
d.
//suggested corrections made.. still not working..
#includeiostream
#includeconio.h
#includemath.h
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int j,s,d=n-1; while((d1)==0) d=1;
s=n/d;for(j=0;1js;j++); s=j;
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{if(primes[i]=n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
int r;
for(r=1;rs;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k2000;k++)
if(is_prime(k))
printf(%d is %d\n,k,is_prime(k));
getch();
}
On 1/18/12, Terencetechnic@gmail.com wrote:
@Sourabh
m=2^s***d
primes[i]**n
On 2012-1-18 19:39, Sourabh Singh wrote:
@Terrence
sry i didn't explain what s,d were they were also wrong i ws
calculating for n not n-1
earlier n=2^s+d
nw m=n-1; for odd n
m=2^s+d;
//suggested corrections made.. still not working..
#includeiostream
#includeconio.h
#includemath.h
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int m=n-1;
int s,d;
for(s=0;1sm;++s); s--;d=(m%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{if(primes[i]n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k20;k++) printf(%d is %d\n,k,is_prime(k)); getch();}
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ sunny agrawal
you are right. but i have used check an also . no improvement .
i think algo is wrong in later part.. somewhere..
@ Terence
1) pow may not work for big n but , m just checking for n=1..200
just to check wether algo is right.. and it's not working even for
n=7,19...
2) d,s are also coming fine for small values.. of n
3) for x i have used... 64bit integer.. uint64_t in it's declaration.
i just want to get algo right first then bother about big n ;-)
On 1/18/12, Terencetechnic@gmail.com wrote:
1. the computing of d is incorrect.
d = n-1;
while((d1)==0) d=1;
2. the accuracy of pow is far from enough. you should implement your
own
pow-modulo-n method.
3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
need to implement your own multiply method in this case.
On 2012-1-18 18:15, Sourabh Singh wrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its
given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singhsinghsourab...@gmail.comwrote:
@ALL hi everyone m trying to make prime checker based on
miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#includeiostream
#includeconio.h
#includemath.h
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0(n+1)%6!=0) || n2)
return 0;
int s,d;
for(s=0;1sn;++s); s--;d=(n%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
printf(x is %llu\n,x
Re: [algogeeks]
It just uses the binary form of integer. (ex. 21=2^4+2^2+2^0)
start from 2^0=1, iteratively calculate g(k) = x^(2^k) = g(k-1)^2 (mod p)
and check the bits of n to see if it updates the final result of x^n (mod p)
take 3^21(mod7) as example: (initially r = 1)
kg(k) r
0 3 1*3=3
1 2 3
2 4 3*4=5
3 2 5
4 4 5*4=6
3^21 = 6 (mod7)
another way is using b^2k = (b^2)^k*1 and b^(2k+1) = (b^2)^k*b.
to calculation y = x^n (mod p), we maintain the relation y=b^k*r, and
reduce k.
initially y = x^n * 1, (b,k,r) = (x,n,1)
using above formula, we got (b,2k,r) - (b^2, k, r) and (b,2k+1,r) -
(b^2, k, r*b)
when k = 0, we got y=b^0*r = r.
take 3^21 (mod 7):
base rank r
3 21 1
9(2)103
45 3
16(2)2 12(5)
41 5
16(2) 0 20(6)
3^21 = 6 (mod 7)
On 2012-1-19 2:54, Sourabh Singh wrote:
@all sorry .. 21 is prime :-)
hw can above algo be well implemented to get mpow function...
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@All
pow() mod is giving problem...
found an algo .. is some1 intrested to discuss...
Example:
Take 3^21 (mod 7)
3^2= 9 = 2(mod 7),
3^4= (3^2)^2 = 2^2 = 4(mod 7)
3^8= (3^4)^2 = 4^2 = 16 = 2(mod 7)
3^16 = (3^8)^2 = 2^2 = 4(mod 7)
So now we have 3^21 = 3^16 * 3^4 * 3 = 4 * 4 * 3 = 48 = 6 (mod 7).
basically.. we can split the power and take individual a^d%n for each
then multiply to get result..
but my question is what if power is prime and big...
On 1/18/12, Terencetechnic@gmail.com wrote:
error in pow.
as long as n 2^31, x*x fits into int64_t, since xn.
On 2012-1-18 20:51, Sourabh Singh wrote:
@ Terence
I belive nw its giving wrong answer for n41 onwards
due to error's in pow and x*x over flow as u already stated...
i guess algo is right nw.. ;-)
thanx again..
On 1/18/12, Sourabh Singhsinghsourab...@gmail.com wrote:
@ thanx got it.. silly mistakes ;-) . missed thought it ws + between s
and
d.
//suggested corrections made.. still not working..
#includeiostream
#includeconio.h
#includemath.h
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0 (n+1)%6!=0) || n2)
return 0;
int j,s,d=n-1; while((d1)==0) d=1;
s=n/d;for(j=0;1js;j++); s=j;
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{if(primes[i]=n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
int r;
for(r=1;rs;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k2000;k++)
if(is_prime(k))
printf(%d is %d\n,k,is_prime(k));
getch();
}
On 1/18/12, Terencetechnic@gmail.com wrote:
@Sourabh
m=2^s***d
primes[i]**n
On 2012-1-18 19:39, Sourabh Singh wrote:
@Terrence
sry i didn't explain what s,d were they were also wrong i ws
calculating for n not n-1
earlier n=2^s+d
nw m=n-1; for odd n
m=2^s+d;
//suggested corrections made.. still not working..
#includeiostream
#includeconio.h
#includemath.h
using namespace std;
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0(n+1)%6!=0) || n2)
return 0;
int m=n-1;
int s,d;
for(s=0;1sm;++s); s--;d=(m%(1s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i6;i++)
{if(primes[i]n)
break;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 || x==n-1)
continue;
for(int r=1;rs;r++)
{ x=(x*x)%n;
if(x==1)
return 0;
if(x==n-1)
break;
}
if(x!=n-1)
return 0;
}
return 1;
}
main()
{for(int k=1;k20;k++) printf(%d is %d\n,k,is_prime(k)); getch();}
On 1/18/12, Sourabh Singhsinghsourab...@gmail.comwrote:
@ sunny agrawal
you are right
Re: [algogeeks] Re: Return index of first mismatch bracket ( or )
And I think the comparing between first unmatched open/close bracket index is not needed. If we found an unmatched close bracket (ie. the stack is empty when encounter a close bracket), we could return current index immediately, since all open brackets before that position are matched and popped out. If we could not find an unmatched close bracket, and the stack is not empty, we examine the stack and return the bottom index (the left most unmatched), or the top index (the inner most unmatch) as needed. On 2011-12-22 13:27, Terence wrote: Then what's your output for test case ()(()? On 2011-12-22 12:45, atul anand wrote: i guess there is no need of stack , we can take a variable say top; increment top when open bracket occur ( and decrement when close bracket ) occurs. keep track of first close bracket mismatch i.e when top is zero and current bracket is ). if top!=0 report min(index,top); On Tue, Dec 20, 2011 at 11:06 PM, shady sinv...@gmail.com mailto:sinv...@gmail.com wrote: true, we have to look at the entire string to find the first mismatch, and its meaning depends on how you interpret it... either way stack will solve it :) On Dec 20, 10:32 pm, Arun Vishwanathan aaron.nar...@gmail.com mailto:aaron.nar...@gmail.com wrote: @shady: I guess first mismatch means the innermost open brace that doesnt have a close brace. U cannot know that the first brace does not have a closing one unless u look at the entire string. On Tue, Dec 20, 2011 at 9:23 AM, shady sinv...@gmail.com mailto:sinv...@gmail.com wrote: ( ( ) ( ( ) ( ( ) ) ( ) for this SAMM faulty index is 0, because the first bracket has itself found no matching @atul ( ( ( () ) ) for this first bracket is faulty as it couldn't find a closing bracket, , , you can keep a stack with map as element stack mapint, char mapint, char where integer is the index of the bracket, which is stored as char idea is similar to don's. On Tue, Dec 20, 2011 at 10:42 PM, atul anand atul.87fri...@gmail.com mailto:atul.87fri...@gmail.comwrote: there are multiple mismatch or only one mis-match in the input string. if the given string as below :- ( ( ( () ) ) - for this is missing match is for 1st , 2nd or 3rd bracket. what would be the answer for this. On Tue, Dec 20, 2011 at 8:10 PM, zeroByZero shri.nit...@gmail.com mailto:shri.nit...@gmail.comwrote: In a given string arrary arr[] = ((()()) or any other string return index for which no match is found as for this example is index 0 and for ()()()(() is index 6 -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group
Re: [algogeeks] Re: Return index of first mismatch bracket ( or )
Then what's your output for test case ()(()? On 2011-12-22 12:45, atul anand wrote: i guess there is no need of stack , we can take a variable say top; increment top when open bracket occur ( and decrement when close bracket ) occurs. keep track of first close bracket mismatch i.e when top is zero and current bracket is ). if top!=0 report min(index,top); On Tue, Dec 20, 2011 at 11:06 PM, shady sinv...@gmail.com mailto:sinv...@gmail.com wrote: true, we have to look at the entire string to find the first mismatch, and its meaning depends on how you interpret it... either way stack will solve it :) On Dec 20, 10:32 pm, Arun Vishwanathan aaron.nar...@gmail.com mailto:aaron.nar...@gmail.com wrote: @shady: I guess first mismatch means the innermost open brace that doesnt have a close brace. U cannot know that the first brace does not have a closing one unless u look at the entire string. On Tue, Dec 20, 2011 at 9:23 AM, shady sinv...@gmail.com mailto:sinv...@gmail.com wrote: ( ( ) ( ( ) ( ( ) ) ( ) for this SAMM faulty index is 0, because the first bracket has itself found no matching @atul ( ( ( () ) ) for this first bracket is faulty as it couldn't find a closing bracket, , , you can keep a stack with map as element stack mapint, char mapint, char where integer is the index of the bracket, which is stored as char idea is similar to don's. On Tue, Dec 20, 2011 at 10:42 PM, atul anand atul.87fri...@gmail.com mailto:atul.87fri...@gmail.comwrote: there are multiple mismatch or only one mis-match in the input string. if the given string as below :- ( ( ( () ) ) - for this is missing match is for 1st , 2nd or 3rd bracket. what would be the answer for this. On Tue, Dec 20, 2011 at 8:10 PM, zeroByZero shri.nit...@gmail.com mailto:shri.nit...@gmail.comwrote: In a given string arrary arr[] = ((()()) or any other string return index for which no match is found as for this example is index 0 and for ()()()(() is index 6 -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Building a max heap takes O(n) time irrespective of the array being sorted / unsorted.
http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap The algorithm of heap-building presented in most books is O(n). On 2011-9-16 12:52, Ankuj Gupta wrote: is talks of more tighter bound of O(nlogn) On Sep 15, 11:24 pm, sunny agrawalsunny816.i...@gmail.com wrote: Read CLRS On Thu, Sep 15, 2011 at 11:51 PM, saurabh agrawalsaurabh...@gmail.comwrote: Building a max heap takes O(n) time irrespective of the array being sorted / unsorted. Can someone prove that. I already know that Heap can be constucted in o(n*log(n)) time. -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Math Puzzle
P^2/QR+Q^2/PR+R^2/PQ = (P^3+Q^3+R^3)/PQR = ((P+Q+R)(P^2+Q^2+R^2-PQ-QR-PR)+3PQR)/PQR = 3 On 2011-9-15 13:29, rahul sharma wrote: hw? On Thu, Sep 15, 2011 at 10:57 AM, Tamanna Afroze afroze...@gmail.com mailto:afroze...@gmail.com wrote: yah the ans is 3 -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: How to use asm in spoj
CONT1D and D1ONE already defined When compile with -O2, gcc 4.3.2 tries to inline short functions like gcd(). Thus the labels CONT1D and D1ONE get redefined. 1) Try gcc 4.0.3. or 2) use local labels instead. eg. __asm__ __volatile__ ( movl %1, %%eax; 0: cmpl $0, %%ebx; je 1f; ... jmp 0b; 1: movl %%eax, %0; : =g (result) : g (a), g (b) ); On 2011-6-18 10:02, saurabh singh wrote: I am using standard gcc 4.3.2 and the code does not requires any flag to be required.I also checked the alias if gcc has been aliased to be used with some option,but that was not the case.My operating system is ubuntu.The error I get is CONT1D and D1ONE already defined. I wonder if spoj has a modified gcc which uses the nasm assembler instead of the standard assembler packed with gcc?I have put the problem on spoj forum few days back but no one has replied since On Sat, Jun 18, 2011 at 3:06 AM, DK divyekap...@gmail.com mailto:divyekap...@gmail.com wrote: What compiler are you using? Version, compile options etc. -- DK -- 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/-/Wf2PvNNjTikJ. To post to this group, send email to algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find shortest substring that is only occurring once. in Given String
Traversal the suffix tree is enough. All substrings from root to leaf (including at least 1 character of leaf node) occur only once. Choose the shortest among them. On 2011-6-15 5:28, T3rminal wrote: @bittu How can u find the shortest substring from the tree in 0(n). Can u please elaborate a bit ? On Jun 14, 6:03 pm, bittushashank7andr...@gmail.com wrote: I found one interesting question Given a string s , return the shortest substring that is only occurring once. Examples: s=aabbabbaab gives either bab or baa s= gives My Approaches Generate All Possible SubStrings O(N^2) puts all substrings into hashtable keep incrementing counter for each substring , return substring with counter 1 memory O(N) Not efficient Create Suffix Tree Seems to be Efficient Solution Only You Need to do Create Tree then we can find the shortest substring that is only occurring once. in O(n) time PS: let me other approaches,suggestion Thanks Shashank CSE,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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Please explain this problem
a,b,c,d,e,f do not need to be distinct. (It is possible that a=b=c=d=e=f, see Example 1) On 2011-6-10 12:01, saurabh singh wrote: Problem link- ABCDEF https://www.spoj.pl/problems/ABCDEF/ Can someone please explain this problem.The problem says a,b,c,d,e,f belongs to S.But what if size of S is smaller than 6? I know i am missing sumthing very trivialhelp plz. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser] Salman age puzzle 7 june
84 years. The well known Diophantus Riddle: http://en.wikipedia.org/wiki/Diophantus#Biography On 2011-6-7 16:03, Lavesh Rawat wrote: ***Salman age puzzle * ** *** *** ** ***salman's youth lasted one sixth of his life. He grew a beard after one twelfth more. After one seventh more of his life, he married. 5 years later, he and his wife had a son. The son lived exactly one half as long as his father, and salman died four years after his son. How many years did salman live? *** *Update Your Answers at* : Click Here http://dailybrainteaser.blogspot.com/2011/06/salman-age-puzzle-7-june.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
Try this case:
1000 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1
On 2011-5-18 0:27, Kunal Patil wrote:
Ohh..If it is so...Sorry !! I understood it the different way...
But if the question is as mentioned in your 2nd case then also I
believe there is O(n) solution.
Maintain
two pointers: *START* and *END*
two variables: max1 and max2
Assume arr[MAX_SIZE] to be the array containing the given elements.
Algorithm:
*1) Initially, make START point to zeroth element and END pointing to
last element of the array.
2) Calculate max1 as:
2a) Compare arr[**START**] and arr[**END**].
If arr[**START**] arr[**END**]
{
max1 = **END**- **START**;
Jump to 3rd step
}
2b) If arr[**START**] = arr[**END**]
{
**END**-- ;
jump to step 2a and repeat this procedure
till **END**!= **START*
* }
3) Reset **END**so that it points to last element of the array.
4) Calculate max2 as:
4a) Compare arr[**START**] and arr[**END**].
If arr[**START**] arr[**END**]
{
max2 = **END**- **START**;
Jump to 5th step
}
4b) If arr**[START**] = arr[**END**]
{
**START**++ ;
jump to step 4a and repeat this procedure
till **START**!= **END*
* }
5) Return max( max1, max2)*
Hope this algo is clear.
This algo makes two passes over the array. Thus it is O(2n) = O(n)..
Let me know if this algo fails for any case you can think of..
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
image/gifimage/gifimage/gifimage/gifimage/gif
Re: [algogeeks] Inversion Count
Guard value error.
L[n1]=;
R[n2]=999;
R[n2] may be merged and counted, if L[1..n1-1] has 999.
On 2011-5-12 19:18, Akshata Sharma wrote:
I tried to solve this problem using merge sort logic, the algorithm is
same as merge sort, only change is in the merge step where i am
counting the inversion_count.
I tested some test cases and I am getting correct answer, but I am
getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/
#includeiostream
using namespace std;
long inversion_count = 0;
void merge(long arr[], long p, long q, long r)
{
long n1 = q-p+1;
long n2 = r-q;
long L[n1];
long R[n2];
for(long i=0;in1;i++)
{
L[i]=arr[p+i];
}
L[n1]=;
for(long i=0;in2;i++)
{
R[i]=arr[q+1+i];
}
R[n2]=999;
long i=0;
long j=0;
long k=p;
while(k=r)
{
if(L[i]=R[j])
{
arr[k]=L[i];
i++;
k++;
}
else if(L[i]R[j])
{
arr[k]=R[j];
j++;
k++;
inversion_count+=n1-i;
}
}
}
void merge_sort(long arr[], long p, long r)
{
if(pr)
{
long q = (p+r)/2;
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
merge(arr,p,q,r);
}
}
int main()
{
int t;
char a;
long n,i;
long arr[22];
scanf(%d,t);
while(t--)
{
scanf(%ld,n);
for(i=0;in;i++)
scanf(%ld,arr[i]);
merge_sort(arr,0,n-1);
coutinversion_count\n;
inversion_count=0;
}
return 0;
}
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Print Hello
@Manikanta: What compiler do you use?
$ gcc test.c
test.c:2: error: initializer element is not constant
$ g++ test.c
$ ./a.out
Hello
$ gcc --version
gcc (GCC) 4.1.1
Copyright (C) 2006 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
g++ treats the source code as C++.
On 2011-3-18 13:34, Manikanta Babu wrote:
@Dondod is right.
It works perfectly. Because printf returns the number of characters
printed so n will be initialized with the number of characters. You
can try out this simple program. I checked its working perfectly.
Thanks,
Mani
On Fri, Mar 18, 2011 at 9:59 AM, .bashrc saurab...@gmail.com
mailto:saurab...@gmail.com wrote:
@Don.Its illegal in c(Or in c99) to initialize a variable with
anything other than a constant.
@pacific No c structures do not support constructor(Or destructor)
On Mar 18, 9:08 am, pacific pacific pacific4...@gmail.com
mailto:pacific4...@gmail.com wrote:
Does C struct have constructor ?
On Fri, Mar 18, 2011 at 12:55 AM, Don dondod...@gmail.com
mailto:dondod...@gmail.com wrote:
int n = printf(Hello\n);
int main()
{
}
On Mar 17, 8:08 am, himanshu kansal
himanshukansal...@gmail.com mailto:himanshukansal...@gmail.com
wrote:
is there any way to print hello in c also wdout writing
anythng in
main()
On Thu, Mar 17, 2011 at 6:34 PM, kunal srivastav
kunal.shrivas...@gmail.com mailto:kunal.shrivas...@gmail.com
wrote:
n...c does not support classes
On Thu, Mar 17, 2011 at 6:10 PM, himanshu kansal
himanshukansal...@gmail.com
mailto:himanshukansal...@gmail.com wrote:
is this possible in c also
On Wed, Mar 16, 2011 at 11:57 PM, Manikanta
manikantabab...@gmail.com
mailto:manikantabab...@gmail.comwrote:
Thats right in C++. How about in C.
On Mar 16, 9:44 pm, kumar anurag
anurag.it.jo...@gmail.com mailto:anurag.it.jo...@gmail.com wrote:
@anurag good.
On Wed, Mar 16, 2011 at 9:28 PM, Anurag atri
anu.anurag@gmail.com mailto:anu.anurag@gmail.com
wrote:
#includeiostream
using namespace std ;
class a
{
public :
a() { couthello;}
}a1;
int main()
{
}
On Wed, Mar 16, 2011 at 8:25 PM, himanshu kansal
himanshukansal...@gmail.com
mailto:himanshukansal...@gmail.com wrote:
How can u print hello in a c/c++ program without
writing a
single
word in main() function
--
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 mailto:algogeeks@googlegroups.com
.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Anurag Atri
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Kumar Anurag- Hide quoted text -
- Show quoted text -
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] RR Scheduling
In this problem, sum can be as large as 5*10^9.
Try breaking the whole interval into several stages (no more than 2*N),
each with a fixed amount of tasks.
Then in each stage, the schedule is a simple loop: A B C D E A B C D E A
B ...
Process each stage in O(1) time, then the total time complexity is O(N).
On 2011-3-21 17:32, saurabh singh wrote:
using scanf and printf and still tle,I am not pretty sure how malloc
or new arrays can speed up execution?
On Mon, Mar 21, 2011 at 2:25 PM, sanchit mittal sm14it...@gmail.com
mailto:sm14it...@gmail.com wrote:
use scanf n printf instead of cin n cout,
malloc array of structures after reading value of n if working in
c else use new in cpp
rest i guess...is ok
On Sun, Mar 20, 2011 at 11:53 PM, ankit sambyal
ankitsamb...@gmail.com mailto:ankitsamb...@gmail.com wrote:
I worked on this problem but cud not get a more efficient algo
than yours.
Plz get back 2 me if u find a better algo.
On Sun, Mar 20, 2011 at 3:24 AM, Akshata Sharma
akshatasharm...@gmail.com mailto:akshatasharm...@gmail.com
wrote:
I tried to solve this problem
https://www.spoj.pl/problems/RRSCHED/
I am getting TLE!! How can I improve my code??
#includeiostream
#includestdio.h
using namespace std;
struct process
{
long time;
int finished;
long elapsed_time;
};
int main()
{
long n,sum=0;
cinn;
struct process prss[5];
for(long i=0;in;i++)
{
scanf(%ld,prss[i].time);
prss[i].finished=0;
sum+=prss[i].time;
}
long index=0;
for(long k=1;k=sum;k++)
{
while(prss[index].finished==1)
index++;
prss[index].time--;
if(prss[index].time==0)
{
prss[index].finished=1;
prss[index].elapsed_time=k;
}
index++;
if(index==n)
index=0;
}
for(long i=0;in;i++)
printf(%ld\n,prss[i].elapsed_time);
return 0;
}
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sanchit Mittal
Second Year Undergraduate
Computer Engineering
Delhi College of Engineering
ph- +919582414494
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser ] 22march
4 * 4 - 7 = 9 Start both sandglasses at the same time. When the 4-minute sandglass is over, flip it to restart timing. Repeat this 3 times. From the moment when the 7-minute sandglass is over, to the moment when the 4-minute sandglass is over for the 4th time, is an interval of 9 minutes. On 2011-3-22 15:35, Lavesh Rawat wrote: ***Hourglass**Problem Solution* * *Having 2 sandglasses: one 7-minute and the second one 4-minute, how can you correctly time 9 minutes? Update Your Answers at : Click Here http://dailybrainteaser.blogspot.com/2011/03/22march.html?lavesh=lavesh Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [brain teaser ] 7march
I will get the gold coin or nothing. On 2011-3-7 16:11, Lavesh Rawat wrote: ***Get Gold Coin **Problem Solution* * *Imagine there are 3 coins on the table: gold, silver, and copper. If you make a truthful statement, you will get one coin. If you make a false statement, you will get nothing. What sentence can guarantee you getting the gold coin? *Update Your Answers at *: Click Here http://dailybrainteaser.blogspot.com/2011/03/7march.html Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Print Hello infinite..................
system(yes Hello); (on Linux) On 2011-3-7 2:09, sudheer kumar wrote: use GOTO On Sun, Mar 6, 2011 at 10:49 PM, UMESH KUMAR kumar.umesh...@gmail.com mailto:kumar.umesh...@gmail.com wrote: How to print Hello Infinite times without using Loop and Recursion function ? -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards chigullapallysudh...@gmail.com mailto:chigullapallysudh...@gmail.com Sudheer -- 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 group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A doubt...
On 2011-3-2 6:22, rgap wrote: Hi, does anybody know when/where to use typedef long long int64; When 64-bit integer is needed. and const long double EPS = 1E-9; When dealing with floating number comparison. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] brain teaser
SeeTen-Hat Variant (http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle#Ten-Hat_Solution). On 2011-3-3 18:02, rajul jain wrote: @naveen but in this question don't know numbers of black and red hats like prison and hat puzzle On Thu, Mar 3, 2011 at 3:25 PM, Naveen Kumar naveenkumarve...@gmail.com mailto:naveenkumarve...@gmail.com wrote: http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle On Thu, Mar 3, 2011 at 3:01 PM, amit kumar amitthecoo...@gmail.com mailto:amitthecoo...@gmail.com wrote: ya at least 10 can be easily freed On Thu, Mar 3, 2011 at 2:18 PM, Manish Pathak pathak@gmail.com mailto:pathak@gmail.com wrote: I think that the last person will tell the color of next front person of him, that means next person will sure that his hat color will be color ,telling by back person. thus person 19 ,17,15,13,11,9,7,5,3,1 th position will get free,and rest amy or may not be... if i am wrong ,tell me On Thu, Mar 3, 2011 at 1:48 PM, freecoder rajuljain...@gmail.com mailto:rajuljain...@gmail.com wrote: You are one of 20 prisoners on death row with the execution date set for tomorrow. Your king is a ruthless man who likes to toy with his people's miseries. He comes to your cell today and tells you: “I’m gonna give you prisoners a chance to go free tomorrow. You will all stand in a row (queue) before the executioner and we will put a hat on your head, either a red or a black one. Of course you will not be able to see the color of your own hat; you will only be able to see the prisoners in front of you with their hats on; you will not be allowed to look back or communicate together in any way (talking, touching.) (The prisoner in the back will be able to see the 19 prisoners in front of him The one in front of him will be able to see 18…) Starting with the last person in the row, the one who can see everybody in front of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT? He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately. If he guesses the right color of the hat on his head he is set free, otherwise he is put to death. And we move on to the one in front of him and ask him the same question and so on… Well, good luck tomorrow, HA HA HA HA HA HA!” Now since you all can communicate freely during the night, can you find a way to guarantee the freedom of some prisoners tomorrow? How many? -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, ManishPathak ** TimesJobs.com manish.pat...@timesgroup.com http://timesgroup.com Mo. 9015687266 -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com
Re: [algogeeks] Re: String of Max Length Which Repeats More Then Onep
@Dave: I think it is to find the longest substring which appears more than once in the given string. @bittu: You could use suffix tree: http://en.wikipedia.org/wiki/Suffix_tree, and find the deepest branch node. or use suffix array: http://en.wikipedia.org/wiki/Suffix_array, and find the length of common prefix of neighbouring elements, then choose the maximum. On 2011-2-25 1:46, Dave wrote: @Bittu: Your statement of the problem doesn't make any sense. Apparently, you are given a string and somehow that string is repeated. Can you clarify it and give an example? Dave On Feb 24, 10:24 am, bittushashank7andr...@gmail.com wrote: Given a string (assume there no spaces or punctuations), write a program that returns the max. length of the string that has repeated more than once. Thanks Shashank -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to identify what is stored in union in c language
Then it should be:
struct UserData
{
uType m_dataType;
union {
int m_intValue;
float m_floatValue;
char m_charValue;
};
} data;
On 2011-2-22 15:29, Rajiv Podar wrote:
Hi Shiva,
There is no as such way to know what type of value is stored in the
Union (as per my knowledge)
But you can try the following code in order to keep track.
enum { INT, FLOAT, CHAR } uType;
union UserData
{
uType m_dataType;
int m_intValue;
float m_floatValue;
char m_charValue;
}; data
So whoever update the UserData union he should update the uType
variable as well and while accessing the value following trick can be
used:
if (m_charValue.m_dataType== INT)
printf(%d\n,data.m_intValue);
if (m_charValue.m_dataType== FLOAT)
printf(%f\n,data.m_floatValue);
if (m_charValue.m_dataType== CHAR)
printf(%c\n,data.m_charValue);
else
printf(bad type %d in utype\n, utype);
I hope this will solve your case.
Thanks Regards,
Rajiv Podar
On Tue, Feb 22, 2011 at 12:15 PM, shiva shivanand.kadwad...@gmail.com
mailto:shivanand.kadwad...@gmail.com wrote:
I have an union with following members
union data
{
int age;
char grade;
}var;
now after some operation which assign value to var(it can assign it
either age or grade), is there any way i can identify whether var
contain age or grade now.
Thanks for the comments..
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to identify what is stored in union in c language
Nope.
The union defines an memory region of 4 bytes (on 32-bit OS).
Access age/grade only specifies which part is retrieved / modified.
You may assign value to age, then retrieve grade, or vice versa.
On 2011-2-22 14:45, shiva wrote:
I have an union with following members
union data
{
int age;
char grade;
}var;
now after some operation which assign value to var(it can assign it
either age or grade), is there any way i can identify whether var
contain age or grade now.
Thanks for the comments..
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] What is the error in the following function
Variable start and hex_buf point to string constant, which can not be
modified.
Change:
char *start = 12.12.12.12.12976665176069214;
char *hex_buf = 65003a0a;
to:
char start[] = 12.12.12.12.12976665176069214;
char hex_buf[] = 65003a0a;
On 2011-2-15 15:01, dinesh bansal wrote:
Hi All,
Can you please point me to the error in the following function. It
gives segmentation fault.
int main()
{
char *start = 12.12.12.12.12976665176069214;
char *hex_buf = 65003a0a;
unsigned short i, j = 0;
int new_len2 = strlen(hex_buf);
for (i = 0; ((j+1) new_len2); i+=2,j+=2)
{
start[i] = hex_buf[j];
start[i+1] = hex_buf[j+1];
}
}
Thanks,
--
Dinesh Bansal
The Law of Win says, Let's not do it your way or my way; let's do it
the best way.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: SPOJ problem code:MAJOR
Try scanf/printf instead of cin/cout.
For huge data set, the IO time matters.
On 2011-2-14 20:09, Akshata Sharma wrote:
link to problem: http://www.spoj.pl/problems/MAJOR/
On Feb 14, 5:03 pm, Akshata Sharmaakshatasharm...@gmail.com wrote:
I am trying to submit my solution but its giving TLE. My implemetation is
O(n).. and i am not able to think a faster algo than this for the problem.
The problem is based on finding the majority element concept. Please help
My code:
#includeiostream
#includestring.h
using namespace std;
struct res{
string boo;
int key;
};
long Majoritycount(int a[], int n)
{
int ctr=1;
int candidate = a[0];
int mindex=0;
for(int i=0;in;i++){
if(a[i]==a[mindex]) ctr++; //match - incr counter
else ctr--; //mismatch - dec counter
if(ctr==0) {
ctr=1;
mindex=i;
candidate=a[i];
}
}
return candidate;
}
int main()
{
struct res result[100];
int t,n,count=0;
int tt,cnt=0;
cint;
tt=t;
while(t0)
{
cinn;
int *arr=new int[n];
for(int i=0;in;i++)
cinarr[i];
int a=Majoritycount(arr,n);
for(int i=0;in;i++)
if(arr[i]==a)
count++;
if(count(n/2))
{
result[t].boo=YES;
result[t].key=a;}
else
{
result[t].boo=NO;
result[t].key=;}
t--;
count=0;
}
for(int i=tt;i0;i--)
{
if(result[i].key!=)
coutresult[i].booresult[i].key\n;
else
coutresult[i].boo\n;
}
return 0;
}
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Bit Manipulation
No. It can be applied to any positive number N.
The solution above splits the numbers by the least significant bit,
choose the group with missing number, and then drop the last bit and
continue.
In this way the set [0,N] is partitioned (almost) evenly into 2 groups:
{2k | k=0,1,...,N/2} and {2k+1 | k=0,1,...(N-1)/2}
and the one with missing number is no more than N/2 numbers.
So the total number of fetch_bit operations is no more than 2N.
On 2011-1-17 15:43, juver++ wrote:
@awesomeandroid
Your solution for Q1 is wrong. It can be applied only for such numbers
N = 2^k, so number should power of 2.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: [Athena 2011]
No need for calculating individual magic(x), just count the number of ordered list L with max(L)=11. Partition those ordered list by its gcd, and check each part, then you can see the trick. On 2011-1-13 11:06, Pratik Bhadkoliya wrote: For example, for 1: divisor is only 1 so, answer is magic(1) = 1 [since (1,1,1,1,1,...,1,1) is the only list possible.] for 2: divisors are 1 and 2 answer is [magic(1) + magic(2)] % 10^8 for 3: answer is [magic(1) + magic(3)] % 10^8 for 4: answer is [magic(1) + magic(2) + magic(4)] % 10^8 by ordered list means : (1,1,1,1,1,1,2) is different from (1,1,1,1,1,,2,1).. that is order of all integers in the list is important. some starting values of magic function magic(1) = 1 magic(2) = 67108862 magic(3) = 2541798719464 magic(4) = 4501057694433304 magic(5) = 1485612519757395128 magic(6) = 169091609518327614304 On Jan 12, 10:23 pm, ashish agarwalashish.cooldude...@gmail.com wrote: didn't get your question dude On Wed, Jan 12, 2011 at 10:39 PM, Pratik Bhadkoliya pkbhadkol...@gmail.comwrote: (a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z) is an ordered list of positive integers Let magic(value) denote the number of such ordered lists that exist such that gcd(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=1 AND max(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z)=value Find the divisors of 11(18 -digits) . For each of the divisors D , compute magic(D) . Find the last 8 digits of the sum of all the magic(D) computed . -- 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.comalgogeeks%2Bunsubscribe@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] SPOJ PROBLEM-pour1
No BFS, only mathematics. Get the better one out of the 2 choices. (Maybe simulating each of the 2 choices also fits into the time limit, given the input range in the problem page.). On 2011-1-12 9:28, Bharath 2009503507 CSE wrote: i tried solving this prob... http://www.spoj.pl/problems/POUR1/ i tried using BFS...getting TLE in judge.. pl suggest some optimisation or better solution.. Thanks in advance.. Code: http://ideone.com/qIgcU -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Interview Question
@ pacific: Also consider the choice of flipping the node itself. And if an internal node cannot be flipped, it is still possible to flip its value, only the above choice is not taken into consideration.. On 2010-12-28 13:27, pacific pacific wrote: here is my approach : Starting from the root node , if root node need to have a 1 ... if root is an and gate : flips = minflips for left child to have value 1 + minflips for the right child to have value 1 else flips = minimum of ( minflips for left child to have value 1 , minflips for right child to have value 1) For a leaf node , return 0 if the leaf has the value needed else return INFINITY.Also if at any internal node if it is not possible return INFINITY. On Tue, Dec 28, 2010 at 10:06 AM, Anand anandut2...@gmail.com mailto:anandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terence technic@gmail.com mailto:technic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. 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 algogeeks@googlegroups.com mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Interview Question
The description on internal nodes indicates this: The value of an AND gate node is given by the logical AND of its TWO children's values. The value of an OR gate likewise is given by the logical OR of its TWO children's values. On 2010-12-28 13:35, suhash wrote: Your approach is for a binary tree, but the problem statement does not say anything about it. On Dec 28, 10:27 am, pacific pacificpacific4...@gmail.com wrote: here is my approach : Starting from the root node , if root node need to have a 1 ... if root is an and gate : flips = minflips for left child to have value 1 + minflips for the right child to have value 1 else flips = minimum of ( minflips for left child to have value 1 , minflips for right child to have value 1) For a leaf node , return 0 if the leaf has the value needed else return INFINITY.Also if at any internal node if it is not possible return INFINITY. On Tue, Dec 28, 2010 at 10:06 AM, Anandanandut2...@gmail.com wrote: @Terence. Could please elaborate your answer. Bottom up level order traversal helps to get the final root value but how to use it to find minimum flips needed to Obtain the desired root value. On Fri, Dec 24, 2010 at 1:56 AM, Terencetechnic@gmail.com wrote: Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. 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 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Google Interview Question
Let cst[i][j] store the cost to flip node i to given gate j (0-'AND',
1-'OR').
Then: cst[i][j] = 0,if j==gate[i];
cst[i][j] = 1,if j!=gate[i] and ok[i];
cst[i][j] = INFINITY, if j!=gate[i] and !ok[i];
1. To get value 1:
1.1 flip current gate to AND, and change all children to 1
1.2 flip current gate to OR, and change any child to 1.
2. To get value 0:
1.1 flip current gate to AND, and change any child to 0
1.2 flip current gate to OR, and change all children to 0.
So for internal node i:
dp[i][0] = min(cst[i][0]+sum{dp[x][1] for each child x of i},
cst[i][1]+max{dp[x][1] for each child x of i});
dp[i][1] = min(cst[i][0]+max{dp[x][0] for each child x of i},
cst[i][1]+sum{dp[x][0] for each child x of i});
for leaf i:
dp[i][j] = (value[i]==j ? 0 : INFINITY)
On 2010-12-28 13:32, suhash wrote:
This problem can be solved using dp in O(n), where 'n' is the number
of nodes in the tree.
Definitions:
Let gate[i] be a boolean denoting whether the gate at node 'i' is
'AND' or 'OR'. (0-'AND' 1-'OR')
Let dp[i][j] store the minimum no. of swaps required to get a value of
'j' (0 or 1), for the subtree rooted at 'i'.
Let ok[i] be a boolean which denotes whether a flip operation can be
performed at the i'th node or not.
Let i1,i2,i3.ik be the children of node 'i'
Now we have 2 cases:
case 1: ok[i] = 0 (means no flipping possible at node 'i')
In this, we have many cases:
case 1.1: gate[i]=0 (there is an AND gate at node 'i'),
and j=1
this means all children should have a value
1.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]
case 1.2: gate[i]=0 (there is an AND gate at node 'i'),
and j=0
i will discuss this case in the end.
case 1.3: gate[i]=1 (there is an OR gate at node 'i'), and
j=1
this one too, for the end
case 1.4: gate[i]=1 (there is an OR gate at node 'i'), and
j=0
this means all children should have a value
0.
hence dp[i][j]=dp[i1][j]+dp[i2][j]
+.dp[ik][j]
case 2: ok[i] = 1 (means flipping is possible at node 'i')
We have 2 cases in this:
case 2.1: we choose not to flip gate at node 'i'. This
reduces to the 4 cases above(case 1.1, 1.2, 1.3, 1.4)
case 2.2: we choose to flip gate 'i'. Again it is similar
to cases discussed above, except replacing 'AND' by 'OR' and vice
versa
and dp[i][j]=1 + dp[i1][j]+dp[i2][j]
+.dp[ik][j]
Note: 1)Boundary cases for leaf nodes.
2)Top down is easier.
3)If it is impossible to get a value 'j' for subtree rooted
at 'i', then dp[i][j]=INF(some large value)
4)Answer is dp[root][required_value(o or 1)]. If this
quantity is INF, then it is impossible to achieve this.
Now, lets discuss case 1.2:
We have an 'AND' gate and we want a result of 0.
So, atleast one of the children of node 'i' should be 0.
Now create 2 arrays x,y each of size 'k'
x[1]=dp[i1][0], y[1]=dp[i1][1]
x[2]=dp[i2][0], y[2]=dp[i2][1]
.
.
.
x[k]=dp[ik][0], y[k]=dp[ik][1]
Now, let v=min(x[1],x[2],x[3],.x[k]), and 'h' be the index of the
minimum element(x[h] is minimum)
Then, dp[i][j]=v+sigma(f!=h)[min(x[f],y[f])]
The other cases are similar to this!
I can write a code and send if you have doubts.
On Dec 28, 9:36 am, Anandanandut2...@gmail.com wrote:
@Terence.
Could please elaborate your answer. Bottom up level order traversal helps to
get the final root value but how to use it to find minimum flips needed to
Obtain the desired root value.
On Fri, Dec 24, 2010 at 1:56 AM, Terencetechnic@gmail.com wrote:
Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:
Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an AND or an OR gate
associated with it. The value of an AND gate node is given by the
logical AND of its two children's values. The value of an OR gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra
--
You received this message because
Re: [algogeeks] Re: convert binary matrix to zero matrix
when you are talking abt starting from 1 that means that array is 1 based , right ? Right. 111 000 000 Up-left element: 1 Choice 3: 0 (number of 0's on the first row) + 1 (number of 1's on the first column) = 1 Choice 4: 3 (number of 1's on the first row) + 2 (number of 0's on the first column) = 5 Best choice: 3, with 1 toggle. (toggle the first row) 011 100 100 Up-left element: 0 Choice 1: 1 (number of 0's on the first row) + 1 (number of 0's on the first column) = 2 Choice 2: 2 (number of 1's on the first row) + 2 (number of 1's on the first column) = 4 Best choice: 1, with 2 toggles. (toggle the first row and first column) Clarification: In choice 1 and 2, the up-left element is counted twice, ie. 1. number of 0's on the first row and (number of 0's on the) first column 2. number of 1's on the first row and (number of 1's on the) first column The idea is simple: 1) toggle the first row or not? When 1) is decided and applied, 2) toggle columns to make first row all 0. -- the number of 1's in the first row (original or inverted) 3) toggle rows to make first column 0.-- the number of 1's in the first column (after step 2) On 2010-12-25 17:31, Ankur wrote: when you are talking abt starting from 1 that means that array is 1 based , right ? and how did you get the steps calculated. please can you explain, once more take this example, a trivial but albeit will help me explain. 111 000 000 and 011 100 100 if it is feasible for you to reply . On Dec 8, 1:45 pm, Terencetechnic@gmail.com wrote: As Amir pointed out: convert the first row and first column to all zeros In details: 1. choose operations on first row and first column to make up-left element 0. * There are 2 cases, 2 choices for each case: 1. If the up-left element is 0, then 1. toggle both first row and first column, or 2. leave both untouched. 2. If the up-left element is 1, then 3. toggle first row, or 4. toggle first column 2. for each 1 on the first row, toggle the corresponding column, to change first row to all 0s. 3. for each 1 on the first column, toggle the corresponding row, to change first column to all 0s. After above 3 steps, if there are still some 1's, no solution is possible. Otherwise, compare the 2 choice, and choose the minimum steps. --- In fact, we can directly calculate the number of steps in choice a)-d): 1. number of 0's on the first row and first column 2. number of 1's on the first row and first column 3. number of 0's on the first row + number of 1's on the first column 4. number of 1's on the first row + number of 0's on the first column And if we denote the j'th element on i'th row as M[i,j] (start from 1), then the problem have valid solution if and only if: for each element M[i,j], M[1,1]+M[1,j]+M[i,1]+M[i,j] is even. On 2010-12-7 22:59, Prims wrote: Hello Rajan Suppose we have the following matrix 1 1 0 0 If a toggle operation performed on first row, it will change all 1s to 0s and 0s to 1s which result in the followig matrix 0 0 0 0 It is zero matrix and the result. Similarly if a toggle operation is performed on column, it will change all 1s to 0s and 0s to 1s in that particular column. Say you have a function toggle(int , Type) which does the toggle operation. where number is the number of row or column Type can be of Type.Row or Type.Column. Hope it is clear -Prims On Dec 7, 5:33 pm, rajan goswamirajan.goswam...@gmail.comwrote: @Prims Can you please elaborate the problem in detail... What do you mean by toggling row and column... 1 Interchanging a row with some column ? 2 Changing 0s to 1s and 1s to 0s of that row ? or Some thing else ? In both options mentioned above .. no of 1s present in a matrix can not be changed to 0s in any ways ... Please explain the step that can be performed on given matrix. regards, Rajan. On Mon, Dec 6, 2010 at 11:55 PM, Primstopcode...@gmail.comwrote: Amir Could you please explain with an example in detail? On Dec 6, 7:02 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.comwrote: actually a greedy approach for this problem exists: just convert the first row and first column to all zeros if after this step matrix is not a complete zero matrix then it's impossible to make it On Sun, Dec 5, 2010 at 9:10 AM, Primstopcode...@gmail.comwrote: How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps (a step is defined as toggling a
Re: [algogeeks] Google Interview Question
Using the same level order traversal (bottom up), calculating the minimum flips to turn each internal node to given value (0/1). On 2010-12-24 17:19, bittu wrote: Boolean tree problem: Each leaf node has a boolean value associated with it, 1 or 0. In addition, each interior node has either an AND or an OR gate associated with it. The value of an AND gate node is given by the logical AND of its two children's values. The value of an OR gate likewise is given by the logical OR of its two children's values. The value of all of the leaf nodes will be given as input so that the value of all nodes can be calculated up the tree. It's easy to find the actual value at the root using level order traversal and a stack(internal if used recursion). Given V as the desired result i.e we want the value calculated at the root to be V(0 or 1) what is the minimum number of gates flip i.e. AND to OR or OR to AND be required at internal nodes to achieve that? Also for each internal node you have boolean associated which tells whether the node can be flipped or not. You are not supposed to flip a non flippable internal node. 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Ranking Problem
My method is using DP, as Snehal have pointed out.
Suppose S[0..n-1] and T[0..n-1] denotes the score and time for the n
questions respectively.
C[k][s] denotes the maximum total time when choosing from the first k
questions such that the total score do not exceed s.
Then C[0][s] = 0
C[k][s] = max(C[k-1][s], C[k-1][s-S[k-1]]+T[k-1]), s=S[k-1]
= C[k-1][s], sS[k-1]
Suppose the total score/time of all problem is SS/ST and the passing
score is PS
then the answer is (TS - C[n][SS-PS]).
The time complexity is O(n*(SS-PS)).
Actually the 0/1 knapsack problem is a NP-complete problem, and only
have pseudo-polynomial time algorithm, or polynomial time greedy
approximation algorithm.
Refer to http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem
On 2010-12-24 14:00, Ankur Khurana wrote:
how will you choose that ?? without sorting . can you please mention
what method you intend to use to achieve that purpose ?
On Fri, Dec 24, 2010 at 8:16 AM, Terencetechnic@gmail.com wrote:
@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not exceeding (Total
Score - Pass Score), while maximize the sum of time of the subset.
So I do not think O(nlogn) greedy algorithm will solve this problem.
On 2010-12-23 23:38, Ankur Khurana wrote:
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element . then try finding the elements
with max value/time to fulfill the quota of marks. i dont know if this
can be done in O(n) but it can be certainly done in nlogn. any other
views ?
On Thu, Dec 23, 2010 at 9:03 PM, Davindkthar...@googlemail.comwrote:
Thanks for reply. I am looking for O(n) for solution.
Davin
On Dec 23, 8:29 pm, snehal jainlearner@gmail.comwrote:
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davindkthar...@googlemail.comwrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++avpostni...@gmail.comwrote:
Please clarify the problem statement. Provide example.
From the first view problem seems to be unclear.
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Ranking Problem
@Ankur:
It is just 0/1 knapsack problem:
Choose a subset of the questions with sum of scores not exceeding
(Total Score - Pass Score), while maximize the sum of time of the subset.
So I do not think O(nlogn) greedy algorithm will solve this problem.
On 2010-12-23 23:38, Ankur Khurana wrote:
it is just like 0/1 knapsack problem with maximum weight of knapsack
as 40. but in this case that is minimum that we have to calculate.
calculate marks/time for every element . then try finding the elements
with max value/time to fulfill the quota of marks. i dont know if this
can be done in O(n) but it can be certainly done in nlogn. any other
views ?
On Thu, Dec 23, 2010 at 9:03 PM, Davindkthar...@googlemail.com wrote:
Thanks for reply. I am looking for O(n) for solution.
Davin
On Dec 23, 8:29 pm, snehal jainlearner@gmail.com wrote:
hint : use dp
On Thu, Dec 23, 2010 at 8:30 PM, Davindkthar...@googlemail.com wrote:
Marks for Questions(1,6): {10,15,20,25,10,20}
Time for Each Questions(1,6) : { 2, 4,3,4, 2,4}
Passing Marks : 40 Out of 100
Find Questions with minimum time to pass the exam?
On Dec 23, 7:04 pm, juver++avpostni...@gmail.com wrote:
Please clarify the problem statement. Provide example.
From the first view problem seems to be unclear.
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] bits groups
@Saurabh: You are right. I was supposed there were infinite 0's on the left. For 32-bit number, the MSB should also be checked in addition to LSB. Change the first line to: c=1-(N1)-((N31)1); will fix this case. On 2010-12-22 14:44, Saurabh Koar wrote: @Terence: I think the above fails for 0X.Correct me if I m wrong. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: spy in the city
I second Bhavesh. If A knows B, then B is not a spy; else A is not a spy. Thus we can hold an elimination races: for each pair A,B in a match, ask if A knows B, and eliminate as above. In total N-1 matches are needed to decide the final winner. If there is a spy, then the spy is the winner. Otherwise, Another 2N-2 queries are needed to check if the winner is a spy. (or 2N-2-logN, making use of the results of previous matches) On 2010-12-21 22:39, janak wrote: O(N) if everybody knows everybody. O(N^2) if there is no such condition. (i.e. Ask for each person to everybody.) On Mon, Dec 20, 2010 at 9:43 PM, Bhavesh Chauhan chauhan.bhave...@gmail.com mailto:chauhan.bhave...@gmail.com wrote: Every question can eliminate 1 person so you can identify the spy in N-1 questions. Bhavesh On 19 December 2010 23:46, Dave dave_and_da...@juno.com mailto:dave_and_da...@juno.com wrote: Here is an algorithm: spy = 1 for i = 2 to N do if person[spy] knows person[i] then person[i] is not the spy. else if person[i] knows person[spy] then person[spy] is not the spy, set spy = i end if end for for i = 1 to spy-1 do if (person[spy] does not know person[i]) or (person[i] knows person[spy]) then there is no spy, set spy = undefined, break end if end for If there is a spy, you find him in at least 2*N - 2 questions and at most 4*N - 4 questions. Dave On Dec 19, 8:01 am, snehal jain learner@gmail.com mailto:learner@gmail.com wrote: There is a city of N people. The government learnt that some unfriendly nation planted a spy there. A spy possesses unique characteristics: he knows everybody in the city, but nobody knows him. You are a counteragent sent by the government to catch the spy. You may ask the people in the city only one question: Do you know the person X? You may ask as many people as you wish, and one person may be asked as many times as you wish. All the people, including the spy, always answer honestly. How many questions you need to find out who is the spy? -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] bits groups
zero_group(N) {
c=1-(N1); // For even N, zero groups is one more than 1 groups.
while(N) {
d = (N(-N)); // Get the least significiant bit.
N = N+d; // Clear the last 1-group bits
c++; // inc counter.
}
return c;
}
For more bit manipulations, refer to
http://www-graphics.stanford.edu/~seander/bithacks.html.
On 2010-12-21 12:26, AEKME wrote:
How do you count the number of zero group bits in a number? group bits
is any consecutive zero or one bits, for example, 2 is represented
as 010 has two zero bits groups the least
significant bit and the group starts after one.
Also, I am in a bad need for algorithms on bits manipulation if any
one has a reference, please share
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Answer This
I think nobody dies on the first 19 days and everyone dies on the 20th day. (I have no difference with other green-eyes. Why I have to suicide ealier? : ) Given: a) there was at least one green-eyed among them, we could get the following conclusions: 1) If there is exactly 1 green-eye, he committed suicide on the first day. 2) If there is exactly 2 green-eye, they all committed suicide on the second day. ... n) If there is exactly N green-eye, they all committed suicide on the N'th day. 1) is obvious. (No one else he saw is green-eye) For n), each of the N green-eyed persons saw (N-1) green-eye persons. If there were only (N-1) green-eyed persons, they had committed suicide on the (N-1) th day, according to the previous conclusion. So no suicides on the first (N-1) days means there were more green-eyed persons, ie. he is one of them. Each of the N green-eyed persons realized this on the N'th day, and commited suicide. On 2010-12-17 15:34, Iqbal Nouyed wrote: I think Aditya is correct, 1) it never says nobody dies on the first 19 days, just says by the 20th day all the green eyed commit suicide. 2) God said that, He also assured them that there was at least one green-eyed among them. Cheers. On Fri, Dec 17, 2010 at 1:30 PM, Krishna Narasimhan krishna.n...@gmail.com mailto:krishna.n...@gmail.com wrote: Aditya, 1) Nobody dies on the first 19 days everyone dies on the 20th day. 2) Even if it wasnt the case, why should he die just because nobody else did? Is there any condition on THERE SHOULD BE ATLEAST ONE GREEN EYED GUY? On Fri, Dec 17, 2010 at 12:52 PM, Aditya Agrawal adit6...@gmail.com mailto:adit6...@gmail.com wrote: 20 green eys ppl .. At the end of first day person realize no body dies so he is the one with green eye's so he commit sucide ... Similarly on second day .. hence forth 20 people commit suicide in 20 days .. On Fri, Dec 17, 2010 at 11:05 AM, punnu punnu.gino...@gmail.com mailto:punnu.gino...@gmail.com wrote: In an ancient village, there were some green-eyed and blue-eyed persons. One fi ne day, God instructed them, the day on which you come to know that you are a green-eyed, you should commit suicide ... He also assured them that there was at least one green-eyed among them. Well, all the villagers were very intelligent and strict followers of God. But, no one knew color of his own eyes! They didn't have mirrors. They couldn't even communicate with each other. All that they could do is to see color of other's eyes. It happened that on 20th day, all the green-eyed people committed suicide. So, how many green-eyed were there ? -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- I dare do all that may become a man; Who dares do more, is none - Macbeth, twelfh night! Regards Krishna -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at
Re: [algogeeks] Re: What would be the output of the following program..?
Just the opposite.
All the operands are evaluated from left to right, and the right most
operand is returned as the value of whole comma expression.
But remember the operator precedence. Comma is lower than assignment.
So c=--a, b++ - c is equivalent to c=--a; b++ -c;
While c=(--a, b++ -c) is equivalent to --a; c=(b++-c).
#includestdio.h
int main()
{
int a=1,b=2,c=3;
c=--a,b++ - c;
printf(%d %d %d,a,b,c);
return 0;
}
Output: 0 3 0
#includestdio.h
int main()
{
int a=1,b=2,c=3;
c=(--a,b++ - c);
printf(%d %d %d,a,b,c);
return 0;
}
Output: 0 3 -1
On 2010-12-14 22:12, KK wrote:
ya all the exprn is evaluated and left expr is assigned ..
On Dec 13, 9:21 pm, siva vikneshsivavikne...@gmail.com wrote:
#includestdio.h
int main()
{
int a=1,b=2,c=3;
c=--a,b++ - c;
printf(%d %d %d,a,b,c);
return 0;
}
the above code is perfectly valid and prints 0 3 0 ...
but how comma is evaluated and the value assigned to variable 'c' is the
expression evaluated on the RHS of commais there any such rules in C ??
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] linkd list
Here is an O(N^2) algorithm: 1. Sort both A and B. (O(NlogN) or O(N^2), either will work) 2. For each element C[k] in C, find if there is such (i,j) pair that A[i] + B[j] = -C[k]: Start with i = 0 and j = N-1, and loop through the following: a. if A[i] + B[j] -C[k], then j = j-1; b. if A[i] + B[j] -C[k], then i = i+1; c. if A[i] + B[j] = -C[k], then combination A[i]+B[j]+C[k]=0 is found. If i or j goes beyond the valid range in case a or b, then no such combination. The table A[i] + B[j] (i, j=0,1,...,N-1) actually forms an (implicit) Young Tableau. See http://en.wikipedia.org/wiki/Young_tableau and http://placementsindia.blogspot.com/2008/05/search-in-young-tableau-sorted-matrix.html On 2010-12-14 21:33, divya wrote: Given three lists: A, B and C of length n each. Write a function which returns true if any 3 three numbers (1 from each list), sum up to zero. Else return false, if there is no such combination. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] just confirming my answer
I think the answer is (2^m)^(2^n) (or 2^(m*2^n))
For m=1, the answer is 2^2^n.
We can express the function using a truth table with 2^n entries, one
entry for each possible input set.
And each entry has (n+m) fields, represent the n inputs and m outputs.
The m*2^n output fields can be filled freely.
So there are 2^(m*2^n) different truth tables.
On 2010-12-10 18:59, ankit sablok wrote:
Q) an n-input m-output boolean function is defined as follows
(F:{True,False}^n-{True,False}
^m)
find the number of n X 1 functions meaning n inputs and 1 output
and n X m funcrtions meaning n inputs and m outputs
my answer
at any time we can reduce the problems as follows
in the domain we will always be havibg n input variables and the co-
domain can be thought of as having 2 values {True and False}
condisering this i get the number of n X 1 functions as
2^n. Please do suggest me the alternative if i am wrong. thanx in
advance
and the nswer reamins the sam for me in case of finding the number of
n X m functions.
Please help me out if i m wrong in solving this thanx in advance
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid Array
No. You made the same mistake as I.
Try this case: {1, 2, 2, 5, 5}.
Actually, this case defeats the solution of Manmeet's, yours, and mine.
(same min/max, same sum, same xor result)
I think the key point is that the N variable cannot be determined by 1
or 2 equation constraint.
On 2010-12-10 9:44, ADITYA KUMAR wrote:
@jai
yeah, it can be done using count sort logic
but that will take O(n) extra space
which can be avoided by using XOR.
On Fri, Dec 10, 2010 at 3:34 AM, jai gupta sayhelloto...@gmail.com
mailto:sayhelloto...@gmail.com wrote:
Algo:
In first traverse find the min and the max values.
if (max-min) not equals (N-1)
return false
In next traverse map each in a hashtable of size N where
index=key-min. Now in case of collision return false
return true
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Aditya Kumar
B-tech 3rd year
Computer Science Engg.
MNNIT, Allahabad.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: convert binary matrix to zero matrix
As Amir pointed out: convert the first row and first column to all zeros In details: 1. choose operations on first row and first column to make up-left element 0. * There are 2 cases, 2 choices for each case: 1. If the up-left element is 0, then 1. toggle both first row and first column, or 2. leave both untouched. 2. If the up-left element is 1, then 3. toggle first row, or 4. toggle first column 2. for each 1 on the first row, toggle the corresponding column, to change first row to all 0s. 3. for each 1 on the first column, toggle the corresponding row, to change first column to all 0s. After above 3 steps, if there are still some 1's, no solution is possible. Otherwise, compare the 2 choice, and choose the minimum steps. --- In fact, we can directly calculate the number of steps in choice a)-d): 1. number of 0's on the first row and first column 2. number of 1's on the first row and first column 3. number of 0's on the first row + number of 1's on the first column 4. number of 1's on the first row + number of 0's on the first column And if we denote the j'th element on i'th row as M[i,j] (start from 1), then the problem have valid solution if and only if: for each element M[i,j], M[1,1]+M[1,j]+M[i,1]+M[i,j] is even. On 2010-12-7 22:59, Prims wrote: Hello Rajan Suppose we have the following matrix 1 1 0 0 If a toggle operation performed on first row, it will change all 1s to 0s and 0s to 1s which result in the followig matrix 0 0 0 0 It is zero matrix and the result. Similarly if a toggle operation is performed on column, it will change all 1s to 0s and 0s to 1s in that particular column. Say you have a function toggle(int , Type) which does the toggle operation. where number is the number of row or column Type can be of Type.Row or Type.Column. Hope it is clear -Prims On Dec 7, 5:33 pm, rajan goswamirajan.goswam...@gmail.com wrote: @Prims Can you please elaborate the problem in detail... What do you mean by toggling row and column... 1 Interchanging a row with some column ? 2 Changing 0s to 1s and 1s to 0s of that row ? or Some thing else ? In both options mentioned above .. no of 1s present in a matrix can not be changed to 0s in any ways ... Please explain the step that can be performed on given matrix. regards, Rajan. On Mon, Dec 6, 2010 at 11:55 PM, Primstopcode...@gmail.com wrote: Amir Could you please explain with an example in detail? On Dec 6, 7:02 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: actually a greedy approach for this problem exists: just convert the first row and first column to all zeros if after this step matrix is not a complete zero matrix then it's impossible to make it On Sun, Dec 5, 2010 at 9:10 AM, Primstopcode...@gmail.com wrote: How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps (a step is defined as toggling a whole row or whole column -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text - -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Brain Teaser
Good point. Here is one step further:
3. Consider the center 4 numbers(regardless of order): {1,8,a,b},
containing 2 even and 2 odd.
and {a,b} can be chosen from {3,4,5,6}. Then there is only one case:
{1,8,3,6}.
The rest is trivial.
On 2010-11-12 13:26, Amod wrote:
Let me try to formalize it
1. Divide even and odd in halfs
Since any pair of consecutive number consists of an even and an odd
number hence these two cannot be in the same half.
2 Place 1 and 8 on the separation line between even and odd.
Since 1 and 8 have affinity for one number only hence solution is
possible.
Comments and inputs are welcome
On Nov 12, 8:18 am, Amodgam...@gmail.com wrote:
Gr8, guys :)
If any body can formalize the solution, then it would be great
On Nov 12, 12:17 am, Shiv Shankar Prajapati
mca.shivshan...@gmail.com wrote:
Several solutions are possible for it
518 2
736 4
Here we can swap the position of 5-7, 1-3 etc.
On Thu, Nov 11, 2010 at 11:48 PM, jagannath prasad das
jpdasi...@gmail.comwrote:
4 8 3 7
2 6 1 5
On Thu, Nov 11, 2010 at 5:57 PM, sunny agrawalsunny816.i...@gmail.comwrote:
@rohit
4 5 are diagonally adjacent .
On Thu, Nov 11, 2010 at 5:09 PM, Rohit Singhalrsinghal.it...@gmail.comwrote:
1 5 2 6
- - - - - -
3 7 4 8
On Thu, Nov 11, 2010 at 3:16 PM, Abhilasha jain
mail2abhila...@gmail.com wrote:
solution is
5 1 6 2
_ _ _ _
7 3 8 4
On Thu, Nov 11, 2010 at 1:26 PM, Amodgam...@gmail.com wrote:
We have a rectangle
It is divided in eight parts by three vertical and one horizontal line
so that there are 8 chambers.
Now we have numbers from 1-8 to be filled in these chambers.
Rule : No two consecutive numbers must be present either side to side
or diagonal
Invalid situation example
Given 5 at position 2 then 4 cannot occur at any of the give position.
4 5 4
_ _ _ _
4 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Rohit Singhal
B.Tech. Part-IV,
Department Of Electronics Engineering,
Centre of Advanced Studies,
Institute Of Technology, BHU
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Shiv Shankar,
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Learn
(((x 0x)1) | ((x 0x)1)) 5 bit operations in total. On 2010-11-12 16:12, sudhir mishra wrote: Write a program to swap odd and even bits in an unsigned integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc). eg input--- 1234567 7654321 888 output-- 411 12109682 948 -- regards /*Sudhir Mishra*/ MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. image/gif
Re: [algogeeks] Re: modified divide and conquer
No. It is possible. This problem focuses on comparisons of each element. The overall time complexity of merge operation can be as high as O(nlogn), while the normal merge operation has time complexity O(n). But the normal merge operation does not meet the requirement, since in the worst case, (the largest number in one sequence is smaller than the smallest of the other), one element can be included in n comparisons at most. On 2010-11-8 17:00, Gönenç Ercan wrote: does not seem possible, there is a proof that shows that comparison based algorithm can have at best O(nlogn) worst case running time. You can check this proof from algorithms CLRS book. Using this proof, by master's theorem if the merge operation can be implemented in O(lgn) using merge sort with this merge operation, the complexity would be O(logn) contradicting with O(nlogn). So I think its not possible to design such merge algorithm. On Nov 8, 4:58 am, lichenga2404lichenga2...@gmail.com wrote: Suppose we'd like to implement a sorting variant where every element is compared only a small number of times. a) devise a divide and conquer algorithm to merge 2 sorted arrays of length n , which guarantees that every element is included in at most O(log n ) comparisons. b) using this modified merge , prove that Merge-Sort will include element in at most O( (log n)^2) comparisons. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Frequent values spoj
http://www.informatik.uni-ulm.de/acm/Locals/2007/output/
On 2010-10-21 18:59, ANUJ KUMAR wrote:
please give me its output file also so that i can check mine
On 10/21/10, ANUJ KUMARkumar.anuj...@gmail.com wrote:
thanks
On 10/21/10, juver++avpostni...@gmail.com wrote:
Please have a look at this page:
http://www.informatik.uni-ulm.de/acm/Locals/2007/input/.
It contains input data for the problem.
On 21 окт, 00:39, ANUJ KUMARkumar.anuj...@gmail.com wrote:
i am getting wa forhttps://www.spoj.pl/problems/FREQUENT/
here is my code i have used segment trees it would be great if someone
could give me a test case for which my code gives wa.
Thanks in advance.
#includeiostream
#includevector
#includefstream
#includemath.h
#includestring.h
#includestdio.h
using namespace std;
int max(int a,int b)
{
if(ab)return a;
return b;
}
int min(int a,int b)
{
if(ab)return a;
return b;
}
templateclass T
class SegmentTree
{
int **A,size;
public:
SegmentTree(int N)
{
int x = (int)(ceil(log(N)/log(2)));
size = 2*(int)pow(2,x);
A = new int*[size];
for(int x=0;xsize;x++)
A[x]=new int[4];
for(int x=0;xsize;x++)
{
for(int y=0;y4;y++)
A[x][y]=-1;
}
}
void initialize(int node, int start,
int end,
vectorintv1,vectorintv2,vectorintv3)
{
if (start==end)
{A[node][0] =
v1[start];A[node][2]=v2[start];A[node][3]=v3[start];A[node][1]=-1;}
else
{
int mid = (start+end)/2;
initialize(2*node,start,mid,v1,v2,v3);
initialize(2*node+1,mid+1,end,v1,v2,v3);
if (A[2*node][3]=
A[2*node+1][3])
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node][3];}
else
{A[node][0] = A[2 * node][0];A[node][1] = A[2 *
node][2];A[node][2] = A[2 * node+1][2];A[node][3]=A[2*node+1][3];}
}
}
// void pr()
// {
// for(int x=1;xsize;x++) coutx=xA[x][0]
A[x][1]A[x][2]A[x][3]\n;
// }
int query(int node,int i, int j)
{
// coutnode=node i=i j=j\n;
if (iA[node][2] || jA[node][0])
{return -1;}
else if (A[node][1]==-1j=A[node][2]i=A[node][0])
{int
ss=max(i,A[node][0])-A[node][0];ss=ss+A[node][2]-min(j,A[node][2]);return
(A[node][3]-ss);}
else
{ int id1=-1,id2=-1;
if(i=A[node][1])
id1 = query(2*node,i,min(j,A[node][1]));
if(A[node][1]j)
id2 = query(2*node+1,max(i,A[node][1]+1),j);
//coutnode=nodeid1=id1id2=id2\n;
if (id1==-1)
return id2;
if (id2==-1)
return id1;
if (id1=id2)
return id1;
else
return id2;
}
}
};
int main()
{
int i,j,N;
int A[16];
scanf(%d,N);
int M;
scanf(%d,M);
for (i=0;iN;i++)
scanf(%d,A[i]);
vectorintv1;
vectorintv2;
vectorintv3;
int ini=A[0],now,count=1,ip=0;
for(int x=1;xN;x++)
{
now=A[x];
if(now==ini)
count++;
else{ini=A[x];v1.push_back(ip);v2.push_back(x-1);v3.push_back(count);count=
1;ip=x;}
}
v1.push_back(ip);v2.push_back(N-1);v3.push_back(count);
int sz=v1.size();
SegmentTreeint s(sz);
s.initialize(1,0,sz-1,v1,v2,v3);
for(int x=0;xM;x++)
{
(scanf(%d%d,i,j));
printf(%d\n,s.query(1,i-1,j-1));
}
int tmp;
cintmp;
return(0);
}
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: plz explain output
Here is the modified code. Maybe we can find something new.
Code:
#includestdio.h
int main()
{
union {
struct {
int x;
float t;
};
double u;
} a;
a.x=0;
scanf(%f,a.t);
printf(%f\n,a.t);
printf(%f\n,a.u);
a.x=90;
printf(%d\n,a.x);
printf(%f\n,a.x);
printf(%f\n,a.t);
printf(%f\n,a.u);
a.x=1;
printf(%d\n,a.x);
printf(%f\n,a.x);
printf(%f\n,a.t);
printf(%f\n,a.u);
a.x=30;
printf(%d\n,a.x);
printf(%f\n,a.x);
printf(%f\n,a.t);
printf(%f\n,a.u);
a.x=9;
printf(%d\n,a.x);
printf(%f\n,a.x);
printf(%f\n,a.t);
printf(%f\n,a.u);
return 0;
}
Input: 3
Output:
3.00
32.00
90
32.00
3.00
32.00
1
32.00
3.00
32.00
30
32.00
3.00
32.00
9
32.00
3.00
32.00
Input: 32
Output:
32
32.00
8589934592.00
90
8589934592.000172
32.00
8589934592.000172
1
8589934592.02
32.00
8589934592.02
30
8589934592.57
32.00
8589934592.57
9
8589934592.17
32.00
8589934592.17
On 2010-10-11 2:06, Asquare wrote:
As far as I have understood.. Its basically that
once you give the input to t as float, that value is displayed for all
the printf functions except one
because of the %f modifier.. the %f modifier cannot accept x (int) as
a successful argument so it takes the
latest float value..
but in case of
x=30;
printf(%d\n,x);
this printf has %d as modifier so the output is 30.
say t entered is 43.5
so OUTPUT: (as per gcc compiler)
43.5
43.5
43.5
30
43.5
43.5
correct me if im wrong..
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] double tower of hanoi
On 2010-10-8 15:14, snehal jain wrote: A Double Tower of Hanoi contains 2n disks of n different sizes, two of each size. As usual, we’re required to move only one disk at a time, without putting a larger one over a smaller one. a. How many moves does it take to transfer a double tower from one peg to another, if disks of equal size are indistinguishable from each other? Denote the minimum moves as f(n). Like the classical Tower of Hanoi: 1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves 2) move the last 2 disks from Peg 0 to Peg 2 -- 2 moves 3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves f(n) = 2f(n-1) + 2, f(1) = 2 So f(n) = 2^(n+1) - 2 b. What if we are required to reproduce the original top-to-bottom order of all the equal-size disks in the final arrangement? Denote the minimum moves as g(n). It can be proved that, in case a, only the last 2 disks are swapped. The order of all other disks are preserved. So we only need to modify the process to restore the order of the last 2 disks. 1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves 2) move the second last disk from Peg 0 to Peg 1 -- 1 move 3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves 4) move the last disk from Peg 0 to Peg 2 -- 1 move 5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves 6) move the second last disk from Peg 1 to Peg 2 -- 1 move 7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves g(n) = 4f(n-1)+3 = 2^(n+2)-5 -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] double tower of hanoi
@ravindra Great solution. But I need some clarification on my solution to the second. My solution to the second is based on the solution to the first. As I stated, in the solution to the first, only the last 2 disks are swapped, while the order of all other disks are preserved. So moving the same pile of disks twice will preserve the original order of all disks. In step 1) 3) 5) 7) of my solution to the second, the process of a) is performed for the first (2n-2) disks. (No need to preserve order) After step 1)-3) and 5)-7), the order of the first (2n-2) disks is preserved. So order of all disks is preserved after 1)-7). Denote the number of moves as f(n) in case a), and g(n) in case b). We have: f(n) = 2^(n+1) - 2 and g(n) = 4f(n-1)+3. So g(n) = 4*2^n-5 On 2010-10-9 1:56, ravindra patel wrote: @Terence Solution for first one is trivial. Just double the number of moves of typical ToH as each pair requires now 2 moves. In second one the approach is correct but the calculation is wrong. F(n) = 4f(n-1) + 3 = 3(4^n -1)/(4-1) = 4^n-1 = 2^2n -1. This can however be optimized as you can reduce the number of recursions. 1- Move (2n-2, From source, to dest) [f(n-1)] 2- Move the last 2 disks from source to temp (2 moves and order reversed) 3- Move (2n-2, From dest, to source) [f(n-1)] 4- Move the last 2 disks from temp to dest (2 moves and original order recovered) 5- Move(2n-2, From source, to dest) [f(n-1)] so f(n) = 3f(n-1) + 4, f(1) = 4 f(n) = 4(3^n -1)/(3-1) = 2(3^n -1) For larger n(2) this is more efficient. Thanks, - Ravindra On Fri, Oct 8, 2010 at 1:42 PM, Terence technic@gmail.com mailto:technic@gmail.com wrote: On 2010-10-8 15:14, snehal jain wrote: A Double Tower of Hanoi contains 2n disks of n different sizes, two of each size. As usual, we’re required to move only one disk at a time, without putting a larger one over a smaller one. a. How many moves does it take to transfer a double tower from one peg to another, if disks of equal size are indistinguishable from each other? Denote the minimum moves as f(n). Like the classical Tower of Hanoi: 1) move the first (2n-2) disks from Peg 0 to Peg 1 -- f(n-1) moves 2) move the last 2 disks from Peg 0 to Peg 2 -- 2 moves 3) move the (2n-2) disks from Peg1 to Peg 2 -- f(n-1) moves f(n) = 2f(n-1) + 2, f(1) = 2 So f(n) = 2^(n+1) - 2 b. What if we are required to reproduce the original top-to-bottom order of all the equal-size disks in the final arrangement? Denote the minimum moves as g(n). It can be proved that, in case a, only the last 2 disks are swapped. The order of all other disks are preserved. So we only need to modify the process to restore the order of the last 2 disks. 1) move the first (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves 2) move the second last disk from Peg 0 to Peg 1 -- 1 move 3) move the (2n-2) disks from Peg 2 to Peg 1 -- f(n-1) moves 4) move the last disk from Peg 0 to Peg 2 -- 1 move 5) move the first (2n-2) disks from Peg 1 to Peg 0 -- f(n-1) moves 6) move the second last disk from Peg 1 to Peg 2 -- 1 move 7) move the (2n-2) disks from Peg 0 to Peg 2 -- f(n-1) moves g(n) = 4f(n-1)+3 = 2^(n+2)-5 -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Bitwise operator - Adobe
If +,-,*,/ is completely forbidden, I think at least one loop is needed.
Here is my solution:
int next8mult (int n)
{
n = (n ~7);// clear the least 3 bit to make
multiple of 8
int r = 8;
while(r) { // add 8 to n
int r1 = (nr) 1; // get carry bit
n ^= r; // perform bit addition
r = r1; // continue with carry.
}
return n;
}
On 2010-9-25 19:56, Krunal Modi wrote:
Q: Write an algorithm to compute the next multiple of 8 for a given
positive integer using bitwise operators.
Example,
(a) For the number 12, the next multiple of 8 is 16.
(b) For the number 16, the next multiple of 8 is 24.
-
I have written a code using bitwise operators...but, I am not happy
with the solutionIs there any ONE LINE solution ?
Here, is my code.
Approach: shift left till LSB is 0 (say n number of times) then, OR
with 1, finally shift right (same number of times).
#includestdio.h
int main(){
int count,m,n,ans,t;
printf(Enter any number :);
scanf(%d,n);
m=8; //multiple of 8 !!
ans=0;
while(ans=n){
t = m;
while(t){
count=0;
while(ans1){
count++;
ans = ans1;
}
ans = ans|1;
ans = anscount;
t--;
}
}
printf([%d]\n,ans);
return 0;
}
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question make confused !!!!!!!
It is true that there are infinitely many solutions (or zero solutions) (x, y, z) in any case. But what we are interested here is S=x+y+z. Apply y = S-x-z, you get: S/Vp+x(1/Vd-1/Vp)+z/(1/Vu-1/Vp) = T1 S/Vp+x(1/Vu-1/Vp)+z/(1/Vd-1/Vp) = T2 Adding the two, you get 2S/Vp + (x+z)(1/Vd+1/Vu-2/Vp) = T1+T2 When 1/Vd+1/Vu-2/Vp = 0, S = Vp(T1+T2)/2, no matter what x and z are. In this condition, All the solution (S,x,z) forms a line: (the intersection line of above 2 planes) x-z = (T2-T1) / (2(1/Vu-1/Vp)) S = Vp(T1+T2)/2. which is parallel to x-z plane. On 2010-9-16 6:32, Gene wrote: No. Two linear equations in three unknowns will always yield many solutions (or zero solutions). These are essentially plane equations. Two planes intersect in a line (unless they are parallel). You might get a de facto unique solution for some values of Vu, Vd, Vu, T1, T2 from the constraints x,y,z= 0. It would have to lie on an axis. For example, you can aways pick z and find x and y. Using your notation, x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 Subtract to get: x(1/Vd - 1/Vu) + z(1/Vu - 1/Vd) = T1 - T2 then x = [ (T1 - T2) - z(1/Vu - 1/Vd) ] / (1/Vd - 1/Vu) So now you can pick any z and get x. Once you have both of these, plug them in here: y = Vp (T1 - x/Vd - z/Vu) As long as x,y,z= 0, you are in business. On Sep 14, 10:51 pm, Terencetechnic@gmail.com wrote: You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.comwrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.comwrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.comwrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.comwrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.comwrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question make confused !!!!!!!
You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.com wrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.com wrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.com wrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.com wrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.com wrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Question make confused !!!!!!!
So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill then time taken by you will be equal to 15 km on the plain road This is not the truth. 5/72 + 5/64 + 5/56 - 15/64 = 5/72+5/56-10/64 = 10/63-10/64 0 (that is solely due avg of speed of downhill and uphill is = speed on plain road) This only leads to: if u travel 5 hrs uphill and then 5 hrs on plain and then 5 hrs on downhill then distance traveled by you will be equal to travel 15 hrs on the plain road. On 2010-9-15 15:07, rahul patil wrote: the solution seems to be simple. Just try to imagine what is happening You have a road with downhill and uphill. So if u travel 5 km uphill and then 5 km on plain and then 5 km on downhill then time taken by you will be equal to 15 km on the plain road(that is solely due avg of speed of downhill and uphill is = speed on plain road) so the from A to B we reach 40 min earlier due to there more downhill road. while from A to B it is uphill. So let us take x km as the road distance which is not plain. t1 = time to travel x on downhill = x/72 t2 = time to travel x on uphill = x/56 but as given 40min = 2/3 hr = x/56 - x/72 so, x= 168. so it will take 3 hrs to climb while travelling from B to A and plain road distance = 5/3 * 64 = 106.67 km dist = 168 + 106.67 On Wed, Sep 15, 2010 at 8:21 AM, Terence technic@gmail.com mailto:technic@gmail.com wrote: You could also get a unique solution if the car has speed of 72 63 56 in downhill, plain and uphill respectively. I think the speed Vd, Vp, Vu was chosen so that 2Vp = Vd + Vu. But for unique solution, it ought to be 2/Vp = 1/Vd + 1/Vu. Under this condition, we can get the unique S=x+y+z: From x/Vd + y/Vp + z/Vu = T1 x/Vu + y/Vp + z/Vd = T2 We get (1/Vu+1/Vd)(x+z)+2/Vp*y = T1+T2 Apply 2/Vp = 1/Vd + 1/Vu, then 2/Vp(x+y+z)=T1+T2 S=x+y+z = Vp(T1+T2)/2 On 2010-9-15 9:31, Gene wrote: This isn't right. Dropping both y terms is the same as setting y to zero. The answer you get is correct, but there are many others as has been said. You could get a unique solution if the route were constrained to be monotonic (level and up or else level and down). On Sep 14, 4:28 pm, Minotaurausanike...@gmail.com mailto:anike...@gmail.com wrote: Actually the solution is unique. The middle part with the Ys is the same and therefore can be omitted out. Now you are left with 2 equations and 2 unknowns. I used time in minutes and I have x = 1.28, z = 0.30476 units (y can be found out). I guess the trick was 1. to write the equations that Yan did and 2. to recognize that the plain part is the same and hence can be cancelled. On Sep 14, 3:31 am, Yan Wangwangyanadam1...@gmail.com mailto:wangyanadam1...@gmail.com wrote: actually, there are many solutions, just pick up one from them... On Tue, Sep 14, 2010 at 3:23 AM, Abhilasha jain mail2abhila...@gmail.com mailto:mail2abhila...@gmail.com wrote: how can u solve 3 variables using 2 equations? On Tue, Sep 14, 2010 at 3:44 PM, Yan Wangwangyanadam1...@gmail.com mailto:wangyanadam1...@gmail.com wrote: x/72 + y/64 + z/56 = 4 x/56 + y/64 + z/72 = 4+2/3 find a solution to this ... On Tue, Sep 14, 2010 at 2:31 AM, bittushashank7andr...@gmail.com mailto:shashank7andr...@gmail.com wrote: Amazon Interview Question for Software Engineer / Developers A car has speed of 72 64 56 in downhill, plain and uphill respectively . A guy travels in the car from Pt. A to pt. B in 4 Hrs and pt. B to pt. A in 4 Hrs and 40 min. what is the distance between A and B? Regards Shashank -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr
Re: [algogeeks] Re: Amazon Question
The following algorithm traversals both lists twice to find the
intersection point, without modification to the original nodes.
The only assumptions:
1) Head pointer of two list: La, Lb
2) .next point to the next node.
3) .next of the tail node is NULL
intersect(La,Lb)
{
// Find the length difference of two lists
for (pA = La, pB = Lb; pA != NULL pB != NULL; pA = pA-next, pB =
pB-next);
// Discard the beginning of the longer list, to get equal length as
the shorter one.
if(pA != NULL) {
for(pC = pA, pA = La; pC != NULL; pA = pA-next, pC = pC-next);
pB = Lb;
} else if(pB != NULL) {
for(pC = pB, pB = Lb; pC != NULL; pB = pB-next, pC = pC-next);
pA = La;
}
// Traversal both list, until we get a common node, return this node.
// If no such intersection, NULL is returned. (pA,pB will get NULL at
the same time)
for( ; pA != pB; pA = pA-next, pB = pB-next);
return pA;
}
On 2010-9-15 15:50, sharad kumar wrote:
you dont have the structure of the node
typedef struct member node
{
int data;
struct member * next;
}ll;
On Tue, Sep 14, 2010 at 5:57 PM, soundar soundha...@gmail.com
mailto:soundha...@gmail.com wrote:
From first linked list set flag value in each traversal of
node..then start from second linked list suppose if flag value is
already set that is the intersection point
correct me if i am 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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Yahoo!!!! Puzzle
No coding at all. 1) Take out another A pill from the bottle; 2) Split each of the 4 pills into two equal halves, and take one half of echo pill. 3) Collect the other half of the 4 pills for next time. On 2010-9-14 17:22, bittu wrote: You are on a strict medical regimen that requires you to take two types of pills each day. You must take exactly one A pill and exactly one B pill at the same time. The pills are very expensive, and you don't want to waste any. So you open the bottle of A pills, and tap one out into your hand. Then you open the bottle of B pills and do the same thing -- but you make a mistake, and two B pills come out into your hand with the A pill. But the pills are all exactly identical. There is no way to tell A pills apart from B pills. How can you satisfy your regimen and take exactly one of each pill at the same time, without wasting any pills? Write Algorithm to Solve dis Problem in O(1) Regard's Shashank Mani Narayan Don't Be Evil U Can Earn While U learn Computer Science Engineering Birla Institute of Technology,Mesra Cell No. +91-9166674831 -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ternary numbers
Or directly get the last digits from (-1, 0, 1)
100 = 33 * 3 + 1
33 = 11 * 3 + 0
11 = 4 * 3 + (-1)
4 = 1 * 3 + 1
1 = 0 * 3 + 1
Collect those digits together, we get 11X01_3
On 2010-8-31 23:40, Dave wrote:
352/9 = 39-1/9
= 27 + 9 + 3 + 1/9
= 1*3^3 + 1*3^2 + 1*3^1 + 0*3^0 + 0*3^(-1) + 1*3^(-2)
= 1110.01_3
Another example, where -1 comes into play:
Using ordinary ternary {0,1,2} representation:
100 = 1*3^4 + 0*3^3 + 2*3^2 + 0*3^1 + 1*3^0
= 10201_3{0,1,2}
Now transform into the {0,1,-1} representation by replacing 2 with -1
and adding 1 to the place digit to the left, propagating a carry if
necessary. I.e., if as you add 1 to the digit to the left it becomes
2, then you repeat the transformation on that digit as well. I'll
write 1 bar as X.
= 11X01_3{0,1,-1}
Dave
On Aug 30, 6:46 pm, Raj Nrajn...@gmail.com wrote:
In ternary number representation, numbers are represented as 0,1,-1.
(Here -1 is represented as 1 bar.) How is 352/9 represented in ternary
number representation?
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Could anyone explain how this code works?????????!!!!
Simple run-length encoding of a ascii picture.
On 2010-9-1 3:49, Albert wrote:
#includestdio.h
main()
{
int a,b,c;
int count = 1;
for (b=c=10;a=- FIGURE?, UMKC,XYZHello Folks,\
TFy!QJu ROo TNn(ROo)SLq SLq ULo+\
UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^\
NBELPeHBFHT}TnALVlBLOFAkHFOuFETp\
HCStHAUFAgcEAelclcn^r^r\\tZvYxXy\
T|S~Pn SPm SOn TNn ULo0ULo#ULo-W\
Hq!WFs XDt! [b+++21]; )
This is the encoding of the picture, each charactor ch 64 (from the
32nd byte, ie. the second row)
represent the length of a sequence of '!' or ' '. (len = ch - 64)
for(; a-- 64 ; )
putchar ( ++c=='Z' ? c = c/ 9:33^b1);
print a sequence of '!' (if b is even) or ' '(if b is odd) with length
(a-64), beginning with sequence of ' ' (b=11),
and alternatively output sequence of '!' and sequence of ' '.
c controls the line wrap by increase from 10 to 90, then rewind to 10
and output a linefeed,
so exactly 80 bytes on each line.
return 0;
}
It just contains two for loop but i cant understand the how it is
working???
help me please.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Will miracle ever print ?
Can this be explained in context of numbers which are out of integer
range ?
This can be explained by integer storage in computer and overflow due to
limited range.
Remember that in computer negative integer is stored as the two's
complement, ie. -x = (~x)+1.
(http://en.wikipedia.org/wiki/2%27s_complement)
Apply this to 0x8000, we get: -0x8000 = 0x7fff+1 =
0x8000.
Note in the last addition, overlap occurs (from 2^31-1 to -2^32)
On 2010-8-31 7:45, Raj N wrote:
Can this be explained in context of numbers which are out of integer
range ?
On Mon, Aug 30, 2010 at 10:36 PM, Yan Wang wangyanadam1...@gmail.com
mailto:wangyanadam1...@gmail.com wrote:
It's miracle can you explain?
On Sun, Aug 29, 2010 at 8:07 PM, Terence technic@gmail.com
mailto:technic@gmail.com wrote:
Try this:
int main()
{
int data = (int)0x8000; // Initialize data during run time
if ( data == -data data!=0)
printf (Miracle!!);
}
On 2010-8-28 1:45, Raj N wrote:
int data; // Initialize data during run time
if ( data == -data data!=0)
printf (Miracle!!);
Will miracle ever print ?
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ternary numbers
First convert 352. 352 = 117 * 3 + 1 = (39 * 3 + 0) * 3 + 1 = ((13 * 3 + 0) * 3 + 0) * 3 + 1 = (((4 * 3 + 1) * 3 + 0) * 3 + 0) * 3 + 1 = 1*3+1) * 3 + 1) * 3 + 0) * 3 + 0) * 3 + 1 So 352 = 111001. Noting 9 = 3^2, thus 352 / 9 = 1110.01 On 2010-8-31 7:46, Raj N wrote: In ternary number representation, numbers are represented as 0,1,-1. (Here -1 is represented as 1 bar.) How is 352/9 represented in ternary number representation? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Converting a decimal number to base -2
No need to handle -1 specially. 6) -2 |-1| 1 | 1| Binary : 11 On 2010-8-30 20:37, ANKIT AGGARWAL wrote: divide each number by -2 until you get -1, or 1 (Remembering that remainder is always +ve) Ex 1) -2 | 2 | 0 | -1 | Interpret -1 as 11 so binary is 110 2) -2 | 3 | 1 |-1| Binary : 111 3) -2 | 4| 0 |-2| 0 | 1| Binary : 110 4) -2 | 5| 1 |-2| 0 | 1| Binary : 101 5) -2 | 6 | 0 |-3 | 1 | 2 | 0 |-1| (Interpret -1 as 11) Binary: 11010 -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] National Instruments: linked list subtraction
On 2010-8-25 20:25, Terence wrote: 1. Calculate the length of both list (A, B). 2. Find the position in the longer list corresponding to the head of shorter list, and copy the previous digits to output list C. (Or for simplicity, appending 0 to the shorter list so as to get the same length as the longer one) 3. Add the two lists into list C without performing carry. 4. Perform carries. For each digit x in sum C, and the previous digit px. a) if x 9, no change to x and px; b) if x 9, x = x - 10, px = px + 1; c) if x ==9, continue to next digit until you come to a digit x' not equal to 9 (or the end of list) if x' 9, x' = x' - 10, px = px + 1, and change all the 9's in between to 0. else, keep all those digits untouched. step 3 and 4 can be merged into one pass. Some clarifications to step 4: 1) Pointer update: Initially x point to the head of list C, and px point to a virtual node with value 0. (If carry to this node is performed, a node of value 1 is added to the head of C) After step 4.a, 4.b, both px and x pointed to the next node. After step 4.c, px advanced to x' and x pointed to the next of x'. 2) Correctness. The operation of step 4 (with above update procedure) ensures px 9 before possible carry. 0. Initially, px = 0 1. After 4.a, px = x 9 2. After 4.b, px = x - 10, while x is sum of 2 digits, so x = 18 = px = 8 3. After 4.c, if x' is not the tail of list, then x' != 9. px = x'(x'9) or px = x'-10(x'9) after update. Similar to above 2 cases, px 9. So after the pass of step 4, we've got the final result. The key point behind the steps is taking groups of (99..9x) as a whole. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] National Instruments: linked list subtraction
Sorry for the mistake of addition vs subtraction. See my previous post for some clarifications on the addition procedure. The procedure of subtraction is similar. To calculate C=A-B: 1. Compare A and B, (first compare length. If length is equal, compare the digits from first to last). If A = B, then output C = 0. (A list of single node 0, or an empty list, depending on the format needed). If A B, then record the sign of C as minus, and swap A and B. 2. Find the position in A corresponding to the head of B, and copy the previous digits of A to output list C. (Or for simplicity, appending 0 to B so as to get the same length as A) 3. Subtract B from A without carry, get intermediate list C. 4. Perform carries on C. For each digit x in sum C, and the previous digit px.(For the first digit x, px = 0) a) if x 0, no change to x and px, both px and x advanced to next node. b) if x 0, x = x + 10, px = px - 1, both px and x advanced to next node. c) if x = 0, continue to next digit until you come to a digit x' not equal to 0 (or the end of list) if x' 0, x' = x' + 10, px = px - 1, and change all the 0's in between to 9. else, keep all those digits untouched. Advance px to x' and x to the next of x'. 5. Remove the initial 0s until C begins with non-zero digits. On 2010-8-25 23:45, Raj N wrote: @Terence: It is subtraction of 2 lists and not addition. N for your logic of addition for x9 you add px+1 and after that if it becomes 9 how do you know the previous of it as you've moved the previous pointer? Can someone comment on my logic ? On Wed, Aug 25, 2010 at 9:10 PM, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: They've mentioned that they're large lists. What if it is a 15 digit number? Its not efficient then. On Wed, Aug 25, 2010 at 8:29 PM, Sathaiah Dontula don.sat...@gmail.com mailto:don.sat...@gmail.com wrote: @Raj, How about doing like below ? Convert A to base 10 number, numA Convert B to base 10 number, numB, Then take the difference numC = abs(numA - numB), Then convert numC to linked list with the digits any comments ?, overflow condition is the problem here. Thanks regards, Sathaiah Dontula On Wed, Aug 25, 2010 at 3:24 PM, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: Input : Two large singly linked lists representing numbers with most significant digit as head and least significant as last node. Output: Difference between the numbers as a third linked list with Most significant digit as the head. Eg: --- Input: A = 5-4-2-0-0-9-0-0 B = 1-9-9 Output: C = 5-4-2-0-0-7-0-1 Required complexity : O(n) Constraint: Reversing linked list is NOT allowed -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] National Instruments: linked list subtraction
1. Calculate the length of both list (A, B). 2. Find the position in the longer list corresponding to the head of shorter list, and copy the previous digits to output list C. (Or for simplicity, appending 0 to the shorter list so as to get the same length as the longer one) 3. Add the two lists into list C without performing carry. 4. Perform carries. For each digit x in sum C, and the previous digit px. a) if x 9, no change to x and px; b) if x 9, x = x - 10, px = px + 1; c) if x ==9, continue to next digit until you come to a digit x' not equal to 9 (or the end of list) if x' 9, x' = x' - 10, px = px + 1, and change all the 9's in between to 0. else, keep all those digits untouched. step 3 and 4 can be merged into one pass. On 2010-8-25 17:54, Raj N wrote: Input : Two large singly linked lists representing numbers with most significant digit as head and least significant as last node. Output: Difference between the numbers as a third linked list with Most significant digit as the head. Eg: --- Input: A = 5-4-2-0-0-9-0-0 B = 1-9-9 Output: C = 5-4-2-0-0-7-0-1 Required complexity : O(n) Constraint: Reversing linked list is NOT allowed -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sorting range of numbers in O(n)
I think count sort is not acceptable (see Ankur's post for explanation), while radix sort fits the requirement. Take the array as an array of 2-digit base n numbers. First sort by the least significant digit (x%n), then the most significant digit (x//n), both using the stable counting sort. The overall time complexity is O(n). On 2010-8-2 17:34, Avik Mitra wrote: You can use count sort or radix sort. Both are of O(n) as running time complexity. You can refer to the book by Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Bitwise Ternary operator
On 2010-7-26 1:46, Tech Id wrote:
int cond (int x, int y, int z) {
return (x==0)*z + (x!=0)*y;
}
Or
int cond (int x, int y, int z) {
return (!x) * z + (!!x)*y;
}
if comparing (==/!=) is not permitted.
On Jul 21, 10:29 pm, BALARUKESHsbalarukesh1...@gmail.com wrote:
Ternary operator- x? y : z
Implement it in a function: int cond(int x, int y, int z); using only
~, !, ^,, +, |,, no if statements, or loops or anything else,
just those operators, and the function should correctly return y or z
based on the value of x. You may use constants, but only 8 bit
constants. You can cast all you want. You're not supposed to use extra
variables, but in the end, it won't really matter, using vars just
makes things cleaner.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: SPOJ:RRSCHED
Don't try to simulate the scheduler on every second. The total execution time can reach 5 * 10^9 sec. Play with small examples, get the task list in execution order, and find the cyclic property of the list. You can solve this problem in O(N) time complexity. On 2010-6-20 18:15, Shravan wrote: Theres a link to the code on the third post. On Jun 20, 3:07 pm, Rohit Sarafrohit.kumar.sa...@gmail.com wrote: No -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 3:22 PM, Shravanshravann1...@gmail.com wrote: Did you see the code which I have posted. On Jun 20, 2:31 pm, Rohit Sarafrohit.kumar.sa...@gmail.com wrote: You must be doing some useless iterations . Otherwise, TLE is too strange for this prob. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 19, 2010 at 9:15 AM, Shravanshravann1...@gmail.com wrote: Even I have implemented it using arrays, but I am getting a TLE. Here's the code http://ideone.com/EfYRa On Jun 19, 8:15 am, Anandanandut2...@gmail.com wrote: It can be done using simple array data structure why do we need complex data structure. Here is how I did. Let me know if I understood correctly. http://codepad.org/rMbTI8PJ On Fri, Jun 18, 2010 at 8:15 AM, Shravanshravann1...@gmail.com wrote: I am trying to solve the problemhttp:// www.spoj.pl/problems/RRSCHED/ . And a naive approach doesn't seem to work .What sort of data structure do I need. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] level order traversal
vertical_traversal(v)
{
stack_init(vstack);
stack_init(tstack);
while(v)
stack_push(vstack, v);
if(v.right)
stack_push(tstack, v.right);
v = v.left;
while(! is_empty(vstack))
visit(stack_pop(vstack));
while(! is_empty(tstack))
vertical_traversal(stack_pop(tstack));
}
On 2010-6-9 16:56, sharad wrote:
can any one tell me how to code for vertical level traversal of a
binary tree?
1
/\
2 3
/ \/ \
45 67
print
4 2156 37
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Puzzle:
No need to enumerate all possible states.
In the final state (2,8,5), each jug is neither full nor empty, while
every valid operation has to fill or empty one jug.
So it is not possible to get this state from any other state by one
valid operation. (As others said, the state before the final one does
not exist)
On 2010-6-10 0:35, Dave wrote:
Assuming that the only moves you can make are to pour the contents of
one jug into another until either the source is empty or the
destination is full, the following are the only positions possible:
0: initial position (15,0,0)
1: starting from 0, pour 10 from jug 1 to jug 2, getting (5,10,0)
2: starting from 0, pour 6 from jug 1 to jug 3, getting (9,0,6)
3: starting from 1, pour 5 from jug 1 to jug 3, getting (0,10,5)
4: starting from 1, pour 6 from jug 2 to jug 3, getting (5,4,6)
5: starting from 2, pour 9 from jug 1 to jug 2, getting (0,9,6)
6: starting from 2, pour 6 from jug 3 to jug 2, getting (9,6,0)
7: starting from 3, pour 10 from jug 2 to jug 1, getting (10,0,5)
8: starting from 4, pour 6 from jug 3 to jug 1, getting (11,4,0)
9: starting from 5, pour 6 from jug 3 to jug 1, getting (6,9,0)
10: starting from 6, pour 6 from jug 1 to jug 3, getting (3,6,6)
11: starting from 7, pour 5 from jug 3 to jug 2, getting (10,5,0)
12: starting from 8, pour 4 from jug 2 to jug 3, getting (11,0,4)
13: starting from 9, pour 6 from jug 2 to jug 3, getting (6,3,6)
14: starting from 10, pour 4 from jug 3 to jug 2, getting (3,10,2)
15: starting from 11, pour 6 from jug 1 to jug 3, getting (4,5,6)
16: starting from 12, pour 10 from jug 1 to jug 2, getting (1,10,4)
17: starting from 13, pour 6 from jug 3 to jug 1, getting (12,3,0)
18: starting from 14, pour 10 from jug 2 to jug 1, getting (13,0,2)
19: starting from 15, pour 5 from jug 3 to jug 2, getting (4,10,1)
20: starting from 16, pour 2 from jug 2 to jug 3, getting (1,8,6)
21: starting from 17, pour 3 from jug 2 to jug 3, getting (12,0,3)
22: starting from 18, pour 2 from jug 3 to jug 2, getting (13,2,0)
23: starting from 19, pour 10 from jug 2 to jug 1, getting (14,0,1)
24: starting from 20, pour 6 from jug 3 to jug 1, getting (7,8,0)
25: starting from 21, pour 10 from jug 1 to jug 2, getting (2,10,3)
26: starting from 22, pour 6 from jug 1 to jug 3, getting (7,2,6)
27: starting from 23, pour 1 from jug 3 to jug 2, getting (14,1,0)
28: starting from 25, pour 3 from jug 2 to jug 3, getting (2,7,6)
29: starting from 27, pour 6 from jug 1 to jug 3, getting (8,1,6)
30: starting from 28, pour 6 from jug 3 to jug 1, getting (8,7,0)
Since {2,8,5) doesn't appear on the list, the puzzle has no solution.
Dave
On Jun 7, 3:32 am, sharadsharad20073...@gmail.com wrote:
: Three containers are of 15,10 and 6 ltrs capacity. Initially its in
configuration (15,0,0). Make it to configuration (2,8,5)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: infix
On 2010-6-11 13:39, BALARUKESH wrote: The increment and decrement method wont work correctly for all cases Ex:- ))a+b(( It works. In this example, the first ')' lead to -1 which indicate the expression is not well formed. This is not a well formed parenthesis... But satisfies the algorithm. The better way is to use a stack... When u find a ' ( ' push it into the stack and when u find a ' )' pop off the top element. Finally the stack should be empty. If [stack has one or more ' ( ' ] or [the stack is empty and exp is not empty] then it is not a well formed parenthesis... The later condition [the stack is empty and exp is not empty] does not necessary lead to ill formed parenthesis. Ex: (a+b)*(c+d). To solve this, you can 1) add an additional pair of parenthesis around the whole expression or 2) change the condition to [the stack is empty and ')' is the next element of the expression] Actually, the increment and decrement method is maintaining the stack size, checking 1) no stack underflow, and 2) stack is empty at the end. So the two method is equivalent. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Removing extra parentheses in an infix string
You can restore the infix expression from the postfix expression calculated, only add parenthesis when necessary in each step. On 2010-6-3 15:35, divya jain wrote: 1.calculte the postfix of given expression. 2.now remove a particular parenthesis from expression and check if the postfix of this expression is equal to the postfix of original expression. if yes then the parenthesis we have removed were extra. if no then the parenthesis were not exta. 3 now remove other parenthesis as step 2 and repeat till u have done this for all parenthesis On 1 June 2010 20:12, Raj N rajn...@gmail.com mailto:rajn...@gmail.com wrote: How to remove extra parentheses in an infix string. For example if it is A+(B*C) parentheses for * is not required as it has higher precedence. Can someone suggest a good routine for 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 mailto:algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Valid permutation of the brackets
Discard illegal prefix as soon as possible, and only proceed with legal one.
* For some position, if the number of '(' and ')' are equal, then do not
try ')' on that position.
* If the number of '(' reaches n, fill the rest positions with ')' to
get a valid permutation.
On 2010-6-3 16:15, Jitendra Kushwaha wrote:
The question is that you have to print all the valid permutations of
the given number of brackets
for example for input 3 we have the output
1 ((()))
2 (()())
3 (())()
4 ()(())
5 ()()()
total five valid permutation
this can be solved in O( 2^(2n) ) where n is number of brackets .
Algo will be like this
1. Try '(' and ')' in every position and print the correct
permutation.Neglect all other permutation
As catalon number is far less then exponential growth ,can anybody
suggest some better algorithm
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This is a different problem, where the requested number with maximum frequency is not necessary majority. On 2010-6-1 13:19, harit agarwal wrote: see this .vote majority algorithm.. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html http://userweb.cs.utexas.edu/%7Emoore/best-ideas/mjrty/index.html -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Why is inorder traversal necessary to reconstruct a binary tree?
The simplest case is: A A / and \ BB both with preorder(and level-order) AB and postorder BA On 2010-4-9 1:23, Himanshu Aggarwal wrote: For a binary tree , if we are given an inorder traversal and a preorder/postorder/level-order traversal, we can always reconstruct back the binary tree. This technique can be used to save and restore the binary tree efficiently. I have read that it is necessary to have an inorder traversal to reconstruct the tree. i.e. if we are given a preorder and a postorder traversal, the binary tree can not be reconstructed. Can someone help me in understanding why this is so? i.e. why is inorder traversal a mandatory requirement. Why can not we reconstruct the tree with a given preorder and a postorder Thanks to everyone for their suggestions and replies. ~Himanshu Aggarwal -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Divide and Conquer problem
Suppose n=2^k, a(0), a(1), ..., a(n-1) are the n teams 1. If there are 1 team, then no matches, 0 days needed; If there are 2 teams, arrange 1 match for them, 1day needed. 2. Split the n teams into 2 groups of equal size, ie. a(0),a(1),...,a(n/2-1) and a(n/2),a(n/2+1),...,a(n-1). 3. Construct the timetable for each group. Merge the 2 timetables to form the timetable of first (n/2-1) days. 4. Arrange inter-group matches for the next n/2 days. One of the choices is: for the next i'th day, let team a(k) plays with a(n/2+(k+i)%(n/2)), k=0,1,...,n/2-1 The final timetable covers exactly (n-1) days. On 2010-4-7 14:50, 难躂 换 wrote: Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. thanks -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Interview question.Provide the solution as per the constraints.
What is the storage structure of your BST?
If each node contains pointers to its left child, right child and
parent, then we can traverse through the tree without recursive or stack.
in_order_traverse()
{
p = root;
last = root-parent = NULL;
while(p) {
if (last == p-parent) { // enter
if(p-left) {
last = p; p = p-left;
} else if(p-right) {
process(p);
last = p; p = p-right;
} else {
process(p);
last = p; p = p-parent;
}
} else if (last == p-left) {
process(p);
if(p-right) {
last = p; p = p-right;
} else if(p-right) {
last = p; p = p-parent;
}
} else {
last = p; p = p-parent;
}
}
}
Combine this with Rahul Singh's algorithm lead to a solution with O(n)
time and O(1) memory
On 2010-3-8 15:11, Nikhil Agarwal wrote:
@all: you cannot traverse through the tree recursively because it has
been mentioned that no extra memory (in recursive calls or stack ) is
allowed.
On Mon, Mar 8, 2010 at 8:42 AM, gaurav gupta
1989.gau...@googlemail.com mailto:1989.gau...@googlemail.com wrote:
Median of BST means : median of Sorted array of elements? is it?
Convert BST into Hight Balance Search Tree then root node will be
your median.
On Sun, Mar 7, 2010 at 2:42 AM, Nik_nitdgp
nikhil.bhoja...@gmail.com mailto:nikhil.bhoja...@gmail.com wrote:
Given a BST (Binary search Tree) how will you find median in that?
Constraints:
-No extra memory.
Algorithm should be efficient in terms of complexity.
Write a solid secure code for it.
No extra memory--u cannot use stacks to avoid recursion.
No static,global--u cannot use recursion and keep track of the
elements visited so far in inorder.
--
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 mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Junior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: missing integers in an unsorted array
No. This works for all cases. Xor is commutative.
On 2010-2-5 13:37, srinivas chintagunta wrote:
I think this works if elements are sorted . Is it correct?
On Mon, Feb 1, 2010 at 5:07 PM, sachin sachin_mi...@yahoo.co.in
mailto:sachin_mi...@yahoo.co.in wrote:
A way to solve this problem would be using xor(exclusive OR)
xor all the elements from 1 to n.Call it A
xor all the elements of the array into a variable B
Now missing element = A xor B
It works this way
xor-ing an element with itself gives 0(p xor p=0)
xor-ing an element with 0 gives the element itself(p xor 0=p)
xor-ing an element with 1 gives the complement of element(p xor
1=complement(p))
Now suppose you are given 4 elements and you have to find the missing
5th element
A=1 xor 2 xor 3 xor 4 xor 5;
B=ar[1] xor ar[2] xor ar[3] xor ar[4];
let array be {2,5,3,1}
thus, B=1 xor 2 xor 3 xor 5;
Now A xor B = (1 xor 1) xor (2 xor 2) xor (3 xor 3) xor (5 xor 5) xor
4 = 0 xor 0 xor 0 xor 0 xor 4 = 4(the missing element).
Regards
Sachin
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Srinivas Chintagunta,
Hyderabad.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merge two BST in O(n) time with O(1)
On 2010-1-28 21:03, Nirmal wrote: Given two binary search trees, how to merge them in O(n) time and O(1) space? It can be done using O(n) space as below, 1. covert BST #1 into linked list or sorted array 2. covert BST #2 into linked list or sorted array 3. merge them... but how to do this in place? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. 1) and 2) is not necessary. Inorder traversal both BST simultaneously, and merge the visited nodes into new BST, just like ordinary sorted array merge. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: multiply by 2 and subtract by 1
The problem can break down to simple case A: A. convert a row of size c elements to all zero using only operations a, b which can further break down to substep B: B. for any two different value x, y in a row, use only operations a, b to convert to same value. Suppose x = y, perform operation a on x until 2*x y. Then if x == y, no more operation is needed; if x y, perform operation b on current row 2*x-y times, now (x, y)-(x', y'), x'=y-x, y'=2y-2x; then perform operation a on x', now both value turns the same. Note that we focus on values instead of elements in the row, when we perform operation on a value, we perform the same operation on all elements in the row having such value. Now repeatly apply substep B on a row of size c elements, convert the least 2 different values to same value, until all values are the same. Then apply operation b until all values are zero. This way we can achieve A. For general case of r*c, just eliminate the rows one by one. ankur aggarwal 写道: I've always wanted to feel the excitement in these interviews. I got a chance, and I liked it. Here is the question: You are given a matrix: r rows, c cols. r x c matrix. Now they all have positive integers. Assume that the computer has no overflow, it can store all possible integer values. Now there are only two operations you can perform on the matrix: a. Multiply one whole column (of size r elements) by 2 aij = aij * 2 b. Decrement a whole row (of size c elements) by 1. aij = aij - 1 Now you are required to find out if it's possible with these operations to convert this matrix into the O matrix. (one with all zeroes in it.) If so, how do you solve it? Or when do you decide to terminate? give the algo.. not 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 unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
