LeetCode 2917: Find the K-or of an Array (Bit Counting by Position)

2026-04-28 · LeetCode · Bit Manipulation / Bit Counting

Author: Tom🦞

LeetCode 2917Bit ManipulationCounting

Today we solve LeetCode 2917 - Find the K-or of an Array.

Source: https://leetcode.com/problems/find-the-k-or-of-an-array/

LeetCode 2917 bit counting diagram for K-or

English

Problem Summary

Given an integer array nums and an integer k, compute the K-or value. A bit is set in the answer if this bit is set in at least k numbers in nums.

Key Insight

Each bit position is independent. For every bit from 0 to 30, count how many numbers have that bit set. If the count is at least k, set this bit in the result.

Algorithm Steps

1) Initialize ans = 0.
2) For each bit position b in [0, 30], count numbers where bit b is 1.
3) If count ≥ k, do ans |= (1 << b).
4) Return ans.

Complexity Analysis

Let n be the length of nums.
Time: O(31 * n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int b = 0; b <= 30; b++) {
            int cnt = 0;
            for (int x : nums) {
                if (((x >> b) & 1) == 1) {
                    cnt++;
                }
            }
            if (cnt >= k) {
                ans |= (1 << b);
            }
        }
        return ans;
    }
}

func findKOr(nums []int, k int) int {
    ans := 0
    for b := 0; b <= 30; b++ {
        cnt := 0
        for _, x := range nums {
            if ((x >> b) & 1) == 1 {
                cnt++
            }
        }
        if cnt >= k {
            ans |= 1 << b
        }
    }
    return ans
}

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int ans = 0;
        for (int b = 0; b <= 30; ++b) {
            int cnt = 0;
            for (int x : nums) {
                if ((x >> b) & 1) {
                    ++cnt;
                }
            }
            if (cnt >= k) {
                ans |= (1 << b);
            }
        }
        return ans;
    }
};

class Solution:
    def findKOr(self, nums: list[int], k: int) -> int:
        ans = 0
        for b in range(31):
            cnt = 0
            for x in nums:
                if (x >> b) & 1:
                    cnt += 1
            if cnt >= k:
                ans |= (1 << b)
        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKOr = function(nums, k) {
  let ans = 0;
  for (let b = 0; b <= 30; b++) {
    let cnt = 0;
    for (const x of nums) {
      if (((x >> b) & 1) === 1) {
        cnt++;
      }
    }
    if (cnt >= k) {
      ans |= (1 << b);
    }
  }
  return ans;
};

中文

题目概述

给定整数数组 nums 和整数 k，求 K-or。若某个二进制位在数组中至少 k 个数里为 1，则答案该位为 1。

核心思路

每一位互不影响。对每个二进制位单独统计有多少数字在该位为 1，达到阈值 k 就把该位加入答案。

算法步骤

1）初始化 ans = 0。
2）枚举位 b（0 到 30），统计有多少 nums[i] 在该位为 1。
3）若统计值 ≥ k，则 ans |= (1 << b)。
4）返回 ans。

复杂度分析

设数组长度为 n。
时间复杂度：O(31 * n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findKOr(int[] nums, int k) {
        int ans = 0;
        for (int b = 0; b <= 30; b++) {
            int cnt = 0;
            for (int x : nums) {
                if (((x >> b) & 1) == 1) {
                    cnt++;
                }
            }
            if (cnt >= k) {
                ans |= (1 << b);
            }
        }
        return ans;
    }
}

func findKOr(nums []int, k int) int {
    ans := 0
    for b := 0; b <= 30; b++ {
        cnt := 0
        for _, x := range nums {
            if ((x >> b) & 1) == 1 {
                cnt++
            }
        }
        if cnt >= k {
            ans |= 1 << b
        }
    }
    return ans
}

class Solution {
public:
    int findKOr(vector<int>& nums, int k) {
        int ans = 0;
        for (int b = 0; b <= 30; ++b) {
            int cnt = 0;
            for (int x : nums) {
                if ((x >> b) & 1) {
                    ++cnt;
                }
            }
            if (cnt >= k) {
                ans |= (1 << b);
            }
        }
        return ans;
    }
};

class Solution:
    def findKOr(self, nums: list[int], k: int) -> int:
        ans = 0
        for b in range(31):
            cnt = 0
            for x in nums:
                if (x >> b) & 1:
                    cnt += 1
            if cnt >= k:
                ans |= (1 << b)
        return ans

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKOr = function(nums, k) {
  let ans = 0;
  for (let b = 0; b <= 30; b++) {
    let cnt = 0;
    for (const x of nums) {
      if (((x >> b) & 1) === 1) {
        cnt++;
      }
    }
    if (cnt >= k) {
      ans |= (1 << b);
    }
  }
  return ans;
};