CHALLENGE : Problem so!ving and efficient code.

Question

(a,b,c) are "triple twins" if ab - c, bc - a, and ca - b are
powers of 2.

Determine all "triple twins" (a, b, c) of positive integers smaller than N. Try to make your code as efficient as possible to reach the highest possible number in sololearn.

Trying all couple if N=1000 means testing 1 billion solutions : you will need to be smarter than this !

Answer 1

ha ha
no one yet showed this result
1 3 3
version 5
limit now 350k.....
😂😂😂😂😂
https://code.sololearn.com/c5yb0WU6rxxv/?ref=app

Answer 2

Okay, after 30 minutes struggling with C#
(because it's my first C# code :)
I did it:

Here we go:

https://code.sololearn.com/cI8eDDB3spkT/?ref=app

###
Oh, and I have a question:
is (a,b,c) and (a,c,b) considered the same (e.g (2,3,2) and (2,2,3))
###

It was a really good challenge.

Answer 3

My try:
https://code.sololearn.com/W33ulWDK8g6Z/?ref=app

Answer 4

https://code.sololearn.com/cFA0wl384DdG/?ref=app

Answer 5

Yes that was like my solution (a little better though) ... but the best way is :
!( n & n-1 )

Answer 6

@sayan, maybe because 1,3,3 is NOT an answer 😂
1*3-3=0 which is not a power of two

Answer 7

If there exits an elegant solution instead of brute-forcing it, then the number properties must follow certain rules which satisfy a set of formula/equation.

However it seems I've ventured too far in Google and it leads me to an IMO question. 👀

https://artofproblemsolving.com/community/c6t79529f6h1112743_find_triples_of_integers

My eyes~~~ ✨💫😫

Answer 8

In fact, as the coming from hell link of @Zephyr said, printing all the solutions if n>=11, or just those which a<=n, b<=n and c<=n would be O(1) complexity 😂

Answer 9

https://code.sololearn.com/c16nECPtN8WW/?ref=app

Answer 10

please do not reveal VCC
let us think the more efficient idea...
DO NOT REVEAL...
JUST WAIT N WAIT N WAIT
PLEASE

Answer 11

third version...
it can calculate upto
1350

https://code.sololearn.com/c54ZueajmF50/?ref=app

Answer 12

n x n/2 x log2(n)

i goes 1 to n
j goes i to n with 2 gap
k goes log2(n)

the reason i used for j in range(i,n,2)
becauae the triplet will always be
either 3 even numbers
or 3 odd numbers
if its a mixture it wont be a tripple twin

Answer 13

Yes, and a big BRAVO for you who were the quickest :p

Answer 14

I must confess i used the IMO files to find not easy number problems...

Answer 15

And I like your challenges @VcC, I would love to see challenges like that to optimize a function (the powerOfTwo for example) :)

Answer 16

For the power of two ... look at the best answer of this post ...
https://www.sololearn.com/discuss/639785/?ref=app

Answer 17

Yup @sayan I failed to find the pattern after sketching on paper over 30 mins due to my limited Maths skill and decided to cheat on web. 😲

Answer 18

note, one working on jsbin plus not in playground https://code.sololearn.com/Wi3XXgCtgR2g/?ref=app

still is weekend: https://www.sololearn.com/Discuss/635638/?ref?app

Answer 19

😂😂☺☺its cool
thats not cheating....u were just knowing.....

Answer 20

This solution works also 😂 :
if(n>1){
cout<<"2, 2, 2"<<endl;
if(n>2){
cout<<"2, 2, 3"<<endl;
if(n > 6){
cout<<"3, 5, 7"<<endl;
if(n > 10){
cout<<"2, 6, 11"<<endl;
}
}
}
}