AND - Magic Bitwise AND Operation
Given n integers, your task is to pick k out of them so that the picked number are minimum when do bitwise AND among all of them.
There are multiple test cases for this problem. The first line of the input contains an integer denoting the number of test cases.
For each test case, there are two integers in the first line: n and k, denoting the number of given integers and the number of integers you are asked to pick out. (1<= n <=40, 1<= k <= n)
The second line contains the n integers. You may assume that all integers are smaller than 260.
Note: There are about one thousand randomly generated test cases. Fortunately 90% of them are relatively small.
For each test case, output only one integer - the smallest possible value.
Input: 2 3 2 5 6 7 8 2 238 153 223 247 111 252 253 247 Output: Case #1: 4 Case #2: 9
Solved using AI algo (Simulated Annealing + Mutation). Feeling like God xD Just mutation is sufficient too..Last edit: 2019-09-19 17:24:04
Getting TLE, any ideas? my submission id: #17763259
Note: "Output" section does not match the Example Output.
Muhammed Hedayetul Islam:
@krishnan: all integers are smaller than 2^60 and non-negative, so doing bitwise AND, result should not exceed 2^60 too.
Whether the range fit in unsigned long long int
I agree with Damian Straszak. The numbers do not seem to be generated uniformly at random. Have you just put in some hand made bad cases, or are the numbers picked from a different distribution than uniform random ?
They're all non-negative.
Can Input integers be negative ?
What do you mean by "randomly generated test cases"? What is the distribution of the n integers?