I will use 0-indexing here.

For n=5n=5, consider the following 55 numbers (shown in binary):

a0=11110a_0= 11110,

a1=11101a_1 = 11101,

a2=11011a_2= 11011,

a3=10111a_3 = 10111,

a4=01111a_4 = 01111

Notice that, there is exactly one off bit in each of the numbers and all those positions of off bits are distinct. So what happens when you take a subset of indices i1<i2<<iki_1 < i_2 < \ldots < i_k and compute the bitwise AND of the values of those indices? Yeah, you will get a number where only the i1,i2,,iki_1, i_2, \ldots, i_k-th bits are off and other bits are on! So bitwise AND of all subsets will be distinct! So that means you can generate all numbers from 00to 2522^5-2. To get 2512^5-1, just add this number. So 66 numbers are enough. You can append any other numbers to get a total of 2n=102n=10 numbers.

So, just set ai=2n12ia_i=2^n-1-2^ifor i=0i=0to n1n-1 and set an=2n1a_n=2^n-1and append any other numbers to get a total of 2n2n numbers.

Pretty cute! Just like you.

Statistics

74% Solution Ratio
Noshin_1703086Earliest, Nov '21
Mushfiqur05Fastest, 0.0s
Noshin_1703086Lightest, 131 kB
octalkeyShortest, 269B
Toph uses cookies. By continuing you agree to our Cookie Policy.