A secure archive stores items on n shelves, numbered 0 through n-1. Opening shelf i requires exactly one physical key for every '1' bit in the binary representation of i -- for instance, shelf 6 is 110 in binary and needs 2 keys, while shelf 5 is 101 and also needs 2 keys. The archivist knows the value of the items on each shelf and wants to know, for a specified key budget k, the combined value of every shelf that needs exactly k keys to open.
The first line contains two space-separated integers n and k. The second line contains n space-separated integers values[0], values[1], ..., values[n-1], the value stored on each shelf.
Print a single integer: the sum of values[i] over every 0-indexed shelf i whose binary representation has exactly k set bits.
Example 1
Input
4 1 5 10 1 5
Expected
11
Explanation
Indices 0,1,2,3 have binary forms 00, 01, 10, 11 with set-bit counts 0, 1, 1, 2. With k=1, indices 1 and 2 qualify, contributing values[1]=10 and values[2]=1, so the answer is 10+1=11.
Example 2
Input
6 0 1 2 3 4 5 6
Expected
1
Explanation
Only index 0 has zero set bits (all other indices from 1 to 5 have at least one '1' bit), so with k=0 the answer is simply values[0]=1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →