AND - Magic Bitwise AND Operation

no tags 

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.


3 2
5 6 7
8 2
238 153 223 247 111 252 253 247

Case #1: 4
Case #2: 9

hide comments
cegprakash: 2019-05-06 03:11:13

Solved using AI algo (Simulated Annealing + Mutation). Feeling like God xD Just mutation is sufficient too..

Last edit: 2019-09-19 17:24:04
Abhishek: 2016-09-22 17:41:41

Getting TLE, any ideas? my submission id: #17763259

LeppyR64: 2014-06-23 19:54:26

Note: "Output" section does not match the Example Output.

Muhammed Hedayetul Islam: 2012-05-31 07:57:35

@krishnan: all integers are smaller than 2^60 and non-negative, so doing bitwise AND, result should not exceed 2^60 too.

krishnan: 2012-05-30 14:50:44

Whether the range fit in unsigned long long int

Walrus: 2012-04-15 07:34:41

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 ?

Sebastian Nowak: 2011-10-11 20:13:47

They're all non-negative.

yash_coder: 2011-10-11 19:25:10

Can Input integers be negative ?

Damian Straszak: 2011-09-19 15:16:18

What do you mean by "randomly generated test cases"? What is the distribution of the n integers?

Added by:Fudan University Problem Setters
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Fudan University Local Contest #3, by g201513