2859. Sum of Values at Indices With K Set Bits
Description
You are given a 0-indexed integer array nums
and an integer k
.
Return an integer that denotes the sum of elements in nums
whose corresponding indices have exactly k
set bits in their binary representation.
The set bits in an integer are the 1
's present when it is written in binary.
- For example, the binary representation of
21
is10101
, which has3
set bits.
Example 1:
Input: nums = [5,10,1,5,2], k = 1 Output: 13 Explanation: The binary representation of the indices are: 0 = 0002 1 = 0012 2 = 0102 3 = 0112 4 = 1002 Indices 1, 2, and 4 have k = 1 set bits in their binary representation. Hence, the answer is nums[1] + nums[2] + nums[4] = 13.
Example 2:
Input: nums = [4,3,2,1], k = 2 Output: 1 Explanation: The binary representation of the indices are: 0 = 002 1 = 012 2 = 102 3 = 112 Only index 3 has k = 2 set bits in its binary representation. Hence, the answer is nums[3] = 1.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 105
0 <= k <= 10
Solutions
Solution 1: Simulation
We directly traverse each index $i$, and check whether the number of $1$s in its binary representation is equal to $k$. If it is, we add the corresponding element to the answer $ans$.
After the traversal ends, we return the answer.
The time complexity is $O(n \times \log n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|