ace.kartik
BAN USER- -3of 3 votes
Answersmultiplication of two numbers without actual multiplication ::
- ace.kartik in India
Using vedic mathematics| Report Duplicate | Flag | PURGE
CareerCup Accountant - 1of 1 vote
AnswersDeck of cards :
- ace.kartik in India for HD
1) Put the first card on the table and next at the bottom of the deck
2) Repeat the above until all the cards are on table.
3) Pick up the cards and repeat steps 1 and 2.
Find after how many iterations the original order is restored.
For Ex ::
1 2 3
1st iteration - 2 3 1
2nd iteration - 3 1 2
3rd iteration - 1 2 3
so after 3 iterations. Find for n.| Report Duplicate | Flag | PURGE
CareerCup Accountant Algorithm
the above logic is right but doesn't work for duplicate characters
I have done few corrections and below is the code
while(1)
{
k=ch[i%siz];
ch[i%siz]=ch[(i+1)%siz];
ch[(i+1)%siz]=k;
i++;
cout << ch << endl;
//cout << sh << endl;
//cin >> st;
if(!strcmp(ch, sh))
break;
count++;
}
cout << count << endl;
}
Didn't mean to post this,
but try for also multiplying large numbers more than 2^64
And upvote the question :)
I've checked your solution, it doesn't give correct output.
Below are the output based on iterations. You can check and verify your code.
Please see IvgenyNovo analysis for O(n) time complexity
No of iterations for 44 are 364
No of iterations for 45 are 403
No of iterations for 46 are 315
No of iterations for 47 are 550
No of iterations for 48 are 48
No of iterations for 49 are 48
No of iterations for 50 are 369
No of iterations for 51 are 1950
excellent work IvgenyNovo!!
you've put some great analysis there.
sorry i didn't see this question was still active or did i miss this?
Ive seen your other soltions as well .. awesome you are!!
I think we can close the case now :)
it is not 2^(n-1) it sum of all previous numbers +1 (explained below)
Take any such combination it will work.
It is not a coincidence that it actually matches 2^(n-1)
a1*x1+a2*x2 .... an*xn=Sn
where x1, x2, x3 ... xn can take 1 or 0.9.
to find
a1, a2, a3 .... an
such that f(Sn)={x1, x2, x3 ... xn}
which can only be done with minimum of binary representation, that is of 2
so if a1 starts with 1
a2 should be a1+1
a3 should be a1+a2+1
.
.
.
an should be a1+a2+a3 .. a(n-1)+1
that is
1, 2, 4, 8, 16 ...
to find f
subtract Sn from (a1+a2+a3...an)
multiply by 10
find the active one's in binary representation of the number we will get the buckets which have fake coins.
Btwn we can use any representation of 3, 4 ... (little bit complicated though)
Nice,
Approach seems to be right. A small improvement though, one iteration would do. Next iterations can be mapped to the first.
for 1 2 3 4
3 4 2 1
2 4 3 1
4 2 3 1
you need to pick up the cards on the table in order.
3 is placed on top of 1.
How did you have 4 2 it should be 2 4.
for example ::
1 2 3 4
1st iteration : 4 2 3 1
2nd iteration : 1 2 3 4
It just takes 2 infact. sorry above logic fails
the above logic is right but doesn't work for duplicate characters
I have done few corrections and below is the code
- ace.kartik March 25, 2014