Hello, there, I recently came up with a task and while solving it, thought the idea was elegant so just wanted to share it here, so people could enjoy it and I hopefully could see more ideas to solve it!
The task goes like this-
Given an array of integers, output distinct indices of two numbers, it they exist, such that bitwise & of both the numbers is greater than or equal to the GCD(Greatest common divisor) of both the numbers.
$$$2<=n<=10^{5}$$$
$$$1<=a_{i}<=10^{9}$$$
Hints-
Hint 1
Hint 2
Hint 3
Hint 4
I will write a solution in a while, but I think the hints must have been enough for you to solve this problem ;). Let me know if there are any other solutions which work, and your thoughts about whether you enjoyed this problem or not.
$$$gcd(0, 10^9) = 10^9$$$
Aaah, you are right, should have said for the given constraints!
Edit-Fixed the element range, thanks!
IMO, it's a cool problem and solution!
It seems that condition $$$0 \le a_i$$$ could be kept as is because if $$$a_j = 0$$$, then $$$0 = a_i \; AND \; 0 = a_i \; AND \; a_j \ge gcd(a_i, a_j) = gcd(a_i, 0) = a_i$$$ could only be true if $$$0>=a_i \Leftrightarrow a_i=0$$$ so with $$$a_j = 0$$$ the only valid pair of $$$(a_i, a_j)$$$ values would be (0, 0) (of course, assuming $$$gcd(0, 0) = 0$$$ technicality) — checking if array has two zeroes is easy.
I might have an idea of possible generalisation(s) (not sure if it could be worth to create a separate problem out of this), perhaps somebody would like to discuss this using CF private message?
Soo...guys, how did it go? Any specific concerns/feedback about the problem? If you want, I can write the solution sketch, in case the hints didn't help. Also, are there any other things which seem to work?
Edit-Thanks for the feedback, great to see that people enjoyed the problem.
I thought about it for about 5 minutes and didn't see anything, then read the hints and got the solution. I think its a nice problem
Very nice problem, I liked the idea very much. Thanks for sharing!!
Very nice problem, thanks for sharing!
I used gcd(x,y) = gcd(x, y-x) <= y-x (for y > x) and arrived at the same solution of any two numbers with same MSB since the difference is definitely less than 2^MSB.
I think rand() works.
It is very good that you have shared your problem with us. But it would have been better if you had sent this problem to Codeforces/Codechef/other resource for competitive programming. This would have been a great task for some contest.
I think the maximum size of an array that doesn't contain valid pairs is small.
Maybe the following idea works: Just sort the numbers in decreasing order and iterate over all pairs while execution time is less than the time limit of the problem. If we don't find any pair, we can assume that the answer doesn't exist.
You have the right intuition but you have to construct an answer. Checkout the hints, since you are close!
Nice!
that's always a cool feeling when one finds a problem idea