Re: [algogeeks] Re: Bit Manipulation
I think Q1 is NP hard problem since the number of bits grows exponentially as the array size increases. On Mon, Jan 17, 2011 at 1:13 PM, juver++ avpostni...@gmail.com 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.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 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
@above, no :) it is solvable in linear 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.
[algogeeks] Re: Bit Manipulation
@juver i am really sorry ,i forget to mention.ya this soln will work only if n is even power of 2. Regards Priyaranjan http://code-forum.blogspot.com On Jan 17, 12:43 pm, juver++ avpostni...@gmail.com 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.
Re: [algogeeks] Re: google paper/...plz help..its urgent
thanks very much.
On Sun, Jan 16, 2011 at 5:04 PM, Lakhan Arya lakhan.a...@gmail.com wrote:
@pacific
Sets of size 2 can have 2 elements common with set of size greater
than 2. for example if set is (1,2) than it is adjacent to sets like
(1,2,3) (1,2,4), (1,2,3,4...n) etc.
So (1,2) is adjacent to (1,2,3), (1,2,4) etc.
On Jan 16, 1:04 pm, pacific pacific pacific4...@gmail.com wrote:
@Lakhan
Why are you not considering sets of size 2 ? Because two sets of size two
cannot have both of the elements as same.
On Sat, Jan 15, 2011 at 9:39 PM, Lakhan Arya lakhan.a...@gmail.com
wrote:
@bittu
I don't think answer of 6th question to be a)
No. of vertices of degree 0 will be those who didnot intersect with
any set i exactly 2 points. All sets of size greater than equal 2 must
intersect with any other set having exactly 2 common elements between
them in exactly 2 points. e.g if a set is (1,2) then it will be
adjacent to (1,2,3) , (1,2,3,4) etc..
The sets of size 0 and 1 cannot intersect in 2 points so they all will
be of degree 0.
Number of Sets of size 0 --- 1
Number of Sets of size 1 --- n
so Total number of vertices n+1.
In the similar way number of connected components will be n+2.
On Jan 15, 8:44 pm, bittu shashank7andr...@gmail.com wrote:
1.c U Can verify by putting n =I where I is positive integer value
say
n=5 try it out its so easy
2 a...what i have understood.
as we know that formal grammar is defined as (N, Σ, P, S)
so For instance, the grammar G with N = {S, A}, Σ = {a, b}, P
with start symbol S and rules
S → aA
A → Sb
S → ε
generates { a^ib^i : =0} so answer is A.
3 expected value doe discrete distributional is defined as
E(i)=sum(pi * xi); so from my points of view ans is 1/n ...Really
Gud
Question one has think..still thinking
4.b -Explaination
Informally the NP-complete problems are the toughest problems in NP
in the sense that they are the ones most likely not to be in P. NP-
complete problems are a set of problems that any other NP-problem can
be reduced to in polynomial time, but retain the ability to have
their
solution verified in polynomial time. In comparison, NP-hard problems
are those at least as hard as NP-complete problems, meaning all NP-
problems can be reduced to them, but not all NP-hard problems are in
NP, meaning not all of them have solutions verifiable in polynomial
time.
(A) is incorrect because set NP includes both P(Polynomial time
solvable) and NP-Complete .
(B) is incorrect because X may belong to P (same reason as (A))
(C) is correct because NP-Complete set is intersection of NP and NP-
Hard sets.
(D) is incorrect because all NP problems are decidable in finite set
of operations.
5. The Most Typical..Still Need Time
6 a zero degree means vertex is not connected from any other vertex
in graph
7.a
8.No Answer Answer Comes to Be 252
15c10,14c9,10c5,10*9*8*7*6 all are greater then from output so
say
No Answer
Correct Me if I am Wrong
Next Time I will Try to provide the solution of 2nd, 5th
problem ..explanations from-others are appreciated
Thanks Regards
Shashank Mani Don't B Evil U Can Earn while U Learn
Computer Science Engg.
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.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.
--
regards,
chinna.
--
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%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards,
chinna.
--
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
Q1: initially compute xor of all the values from 0 to n in a variable Temp so temp = 0^1^2^n let result is used to store the missing number for each ith bit of missing number where i = 0-31 we can find it as following ith bit of result = (xor of all ith bits of values of array) xored with (ith bit of temp) Overall complexity is O(32n) which is same as O(n) -- 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 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
@Sunny Good! -- 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.
[algogeeks] Re: Amazon Interview - Algorithms
here is Working Code Without DP in which we need To Find Out Minimum
Jumps for every Jumps its Finding Maximum Step That Can Be Cover In
A Jump So that No. of Jumps Required is Minimized..
#includestdio.h
int main()
{
int arr[]={1 ,3, 5 ,8, 9, 2, 6 ,7 ,6, 8, 9};
int size=sizeof(a)/sizeof(int);
int i=0;int max,step,j,jump=0;
while( i size)
{ jump++;
max=0;
step=0;
printf( jump=%d \n,jump);
/*computes max distance it can cover in this jump*/
for(j=1;j=arr[i];j++)
{
if(arr[i+j]+jmax)
{
max=arr[i+j]+j;
step=j;
printf( max=%d \n,max);
printf( step=%d \n,step);
}
}
i=i+step;
}
printf(Finally Jump %d \n ,jump);
return 0;
}
Now Remaining Job Need to Be Done is that How to reduce the
complexity..
Thanks 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.
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] help me debug this
i dont knw wt wrong i have done in this simple problem bt its nt being
accepted at uva judge
here is the link to the problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudgeItemid=8category=6page=show_problemproblem=347
please help me debug my code
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmath
using namespace std;
int main()
{
int N,C;// the inputs to be scanned
vectorintprimes;//prime array
vectorints;
while(scanf(%d %d,N,C)==2)
{
int i,j,k;// counters
primes.clear();
s.clear();
for(i=0;i=N;i++)
primes.push_back(i);
for(i=2;iprimes.size();i++)
{
for(j=2;i*jprimes.size();j++)
primes[i*j]=0;
}
for(i=0;iprimes.size();i++)
{
if(primes[i]!=0)
s.push_back(i);
}
/* for(i=0;is.size();i++)
couts[i]endl;*/
printf(%d\n,s.size());
printf(%d %d: ,N,C);
if((2*C)s.size())
{
for(i=0;is.size();i++)
printf(%d ,s[i]);
}
else if((s.size())%2==0)
{
// the evaluate the number of prime numbers to be left out
j=(s.size()-2*C)/2;
for(i=j;i(j+2*C);i++)
printf(%d ,s[i]);
}
else
{
j=(s.size()-2*C+1)/2;
for(i=j;i(j+2*C-1);i++)
printf(%d ,s[i]);
}
printf(\n);
}
getchar();
getchar();
return 0;
}
thnxx 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.
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: help me debug this
Got AC with your code with small corrections to the output - don't use getchar(); output specification says: Each line of output should be followed by a blank line (so, add blank line to match the sample output) you print a whitespace after each number, so the last character in your line is a whitespace (but it is wrong, so take a care of this) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Bit Manipulation
@abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: Bit Manipulation
Yes, I guess following correction in step 1 for Next Smallest should fix it: 1. Find the leftmost 1 [ Not rightmost]. On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: Bit Manipulation
Yes, I guess following correction in step 1 for Next Smallest should fix it: 1. Find the leftmost 1 [ Not rightmost]. On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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.
[algogeeks] Re: Bit Manipulation
Yes, Following should do for next smallest: 1. Find rightmost 01 pair 2. swap these two bits (make it 10) e.g. N=3(011), Next smallest: 5(101) N=10(1010), Next smallest: 12(1100) N=14(01110), Next Smallest: 22(10110) On Jan 18, 12:48 am, juver++ avpostni...@gmail.com wrote: @abobe my solution is wrong when number is even (but it can be avoided with some corrections into an implementation), btw, you have a mistake: N=3(011), Next smallest: 6(110) ,* Should be 101 (5)!* In other cases my version is correct. -- 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: help me debug this
i improved upon my code but still i get a presentation error dunno wts the
judge judging it shows me the correct way when i output test cases on my
compiler but on the judge it says wrong answer or presentation error
#includeiostream
#includecstdio
#includevector
#includealgorithm
#includecmath
using namespace std;
int prime(int N,int C);// the function used to print the cut primes
int main()
{
int N,C;
vectorintv;// used for holding the test cases
while(scanf(%d %d,N,C)==2)
{
v.push_back(N);v.push_back(C);
}
int i;// counter
for(i=0;iv.size();i+=2)
prime(v[i],v[i+1]);
return 0;
}
int prime(int N,int C)
{
vectorintp;
vectorints;
p.clear();s.clear();
int i,j,k;// counters
for(i=0;i=N;i++)
p.push_back(i);
for(i=2;ip.size();i++)
{
for(j=2;i*jp.size();j++)
p[i*j]=0;
}
for(i=0;ip.size();i++)
{
if(p[i]!=0)
s.push_back(i);
}
printf(%d %d: ,N,C);
if((2*C)s.size())
{
for(i=0;is.size();i++)
printf(%d ,s[i]);
}
else if((s.size())%2==0)
{
// the evaluate the number of prime numbers to be left out
j=(s.size()-2*C)/2;
for(i=j;i(j+2*C);i++)
printf(%d ,s[i]);
}
else
{
j=(s.size()-2*C+1)/2;
for(i=j;i(j+2*C-1);i++)
printf(%d ,s[i]);
}
printf(\n\n);
return 0;
}
On Tue, Jan 18, 2011 at 1:05 AM, juver++ avpostni...@gmail.com wrote:
Got AC with your code with small corrections to the output -
don't use getchar();
output specification says: Each line of output should be followed by a
blank line (so, add blank line to match the sample output)
you print a whitespace after each number, so the last character in your
line is a whitespace (but it is wrong, so take a care of this)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
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 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: help me debug this
Redirect your output to the file, and you'll see that at the end of line you
have extra blank.
You need to write something like this (in all sections):
for(i=j;i(j+2*C-1);i++) {
if (i != j) printf( );
printf(%d,s[i]); // note there is no space
}
--
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.
