# Find the K-or of an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-k-or-of-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-the-k-or-of-an-array
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array
---
## Problem
You are given an integer array `nums`, and an integer `k`. Let's introduce **K-or** operation by extending the standard bitwise OR. In K-or, a bit position in the result is set to `1` if at least `k` numbers in `nums` have a `1` in that position.

Return _the K-or of_ `nums`.

**Example 1:** 

**Input:** nums = \[7,12,9,8,9,15\], k = 4 

**Output:** 9 

**Explanation:** 

Represent numbers in binary:

| **Number**     | Bit 3 | Bit 2 | Bit 1 | Bit 0 |
| -------------- | ----- | ----- | ----- | ----- |
| **7**          | 0     | 1     | 1     | 1     |
| **12**         | 1     | 1     | 0     | 0     |
| **9**          | 1     | 0     | 0     | 1     |
| **8**          | 1     | 0     | 0     | 0     |
| **9**          | 1     | 0     | 0     | 1     |
| **15**         | 1     | 1     | 1     | 1     |
| **Result = 9** | 1     | 0     | 0     | 1     |

Bit 0 is set in 7, 9, 9, and 15\. Bit 3 is set in 12, 9, 8, 9, and 15.  
Only bits 0 and 3 qualify. The result is `(1001)2 = 9`.

**Example 2:** 

**Input:** nums = \[2,12,1,11,4,5\], k = 6 

**Output:** 0 

**Explanation:** No bit appears as 1 in all six array numbers, as required for K-or with `k = 6`. Thus, the result is 0.

**Example 3:** 

**Input:** nums = \[10,8,5,9,11,6,8\], k = 1 

**Output:** 15 

**Explanation:**  Since `k == 1`, the 1-or of the array is equal to the bitwise OR of all its elements. Hence, the answer is `10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15`.

**Constraints:**

* `1 <= nums.length <= 50`
* `0 <= nums[i] < 231`
* `1 <= k <= nums.length`

# Approaches
## Brute-Force using String Conversion
This approach involves converting each integer into its binary string representation. After ensuring all binary strings have a uniform length by padding with leading zeros, we can iterate through each bit position (column) and count the number of '1's. If the count for a specific bit position meets the `k` threshold, the corresponding bit is set in the final result. This method is conceptually straightforward but less efficient in terms of memory usage.
**Time:** O(N * B), where N is the number of elements in `nums` and B is the number of bits in an integer (31). Converting N numbers to B-bit strings takes O(N*B). The nested loops for counting also take O(N*B). · **Space:** O(N * B), where N is the number of elements in `nums` and B is the number of bits in an integer (31). We need to store N binary strings, each of length B.
**Pros:** Conceptually simple for those more comfortable with strings than bitwise operations.
**Cons:** High space usage due to storing intermediate binary strings.; String manipulations are generally slower in practice than direct bitwise operations.
### Explanation
This approach works by translating the numbers into a more visual, string-based format. We first convert every number into a 31-bit binary string, padding with leading zeros as necessary. This creates a grid of characters (0s and 1s) where rows are numbers and columns are bit positions. We then iterate through each column (bit position), count the number of '1's, and if this count is at least `k`, we set the corresponding bit in our final integer result.

```java
class Solution {
    public int findKOr(int[] nums, int k) {
        int n = nums.length;
        String[] binaryStrings = new String[n];
        for (int i = 0; i < n; i++) {
            String binary = Integer.toBinaryString(nums[i]);
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < 31 - binary.length(); j++) {
                sb.append('0');
            }
            sb.append(binary);
            binaryStrings[i] = sb.toString();
        }

        int result = 0;
        for (int i = 0; i < 31; i++) { // i represents the bit position from the right (0 to 30)
            int count = 0;
            for (int j = 0; j < n; j++) {
                // Character at index (30 - i) corresponds to bit i
                if (binaryStrings[j].charAt(30 - i) == '1') {
                    count++;
                }
            }
            if (count >= k) {
                result |= (1 << i);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Create an array of strings to store the binary representations of the numbers in `nums`.
*   For each number in `nums`, convert it to a 31-bit binary string, padding with leading zeros to ensure a uniform length of 31. Add this string to the array.
*   Initialize an integer `result = 0`.
*   Iterate from `i = 0` to 30. This loop represents the bit positions, with `i=0` being the least significant bit.
*   Inside this loop, initialize a `count = 0`.
*   Iterate through each binary string in the array.
*   Check the character at index `30 - i` (since bit 0 is the rightmost character). If it's '1', increment `count`.
*   After iterating through all strings, if `count >= k`, set the `i`-th bit in the `result` using the bitwise OR operation: `result |= (1 << i)`.
*   After the outer loop finishes, `result` will hold the K-or value. Return `result`.

## Bit Manipulation using a Count Array
This approach avoids string conversion and uses direct bitwise operations. We use an auxiliary array to keep track of the counts of set bits for each bit position across all numbers in the input array. After populating this count array, we construct the final result by checking which bit positions have a count greater than or equal to `k`. This method improves upon the string-based approach by reducing space complexity.
**Time:** O(N * B), where N is the length of `nums` and B is the number of bits (31). The first nested loop to populate the `bitCounts` array runs N * B times. The second loop to construct the result runs B times. The total complexity is O(N*B). · **Space:** O(B), where B is the number of bits (31). We use an extra array of size B to store the bit counts. Since B is a constant, this is effectively O(1) constant space.
**Pros:** Efficient in terms of time.; Avoids the overhead of string conversions and high memory usage of the string approach.
**Cons:** Requires an auxiliary array for counts, which uses slightly more space than the most optimal approach.
### Explanation
This method is a significant improvement over the string-based approach. It directly manipulates the bits of the integers. The core idea is to first aggregate the counts for each bit position into an array. We iterate through each number in the input, and for each number, we update the counts in a `bitCounts` array for each of its set bits. After this single pass to gather statistics, we build the final result by iterating through our `bitCounts` array and setting a bit in the result if its count is `k` or more.

```java
class Solution {
    public int findKOr(int[] nums, int k) {
        int[] bitCounts = new int[31];
        for (int num : nums) {
            for (int i = 0; i < 31; i++) {
                if (((num >> i) & 1) == 1) {
                    bitCounts[i]++;
                }
            }
        }

        int result = 0;
        for (int i = 0; i < 31; i++) {
            if (bitCounts[i] >= k) {
                result |= (1 << i);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Create an integer array `bitCounts` of size 31, initialized to all zeros.
*   Iterate through each `num` in the `nums` array.
*   For each `num`, iterate through its bits from `i = 0` to 30.
*   If the `i`-th bit is set in `num`, increment `bitCounts[i]`.
*   Initialize an integer `result = 0`.
*   Iterate from `i = 0` to 30 through the `bitCounts` array.
*   If `bitCounts[i] >= k`, set the `i`-th bit in the `result`: `result |= (1 << i)`.
*   Return `result`.

## Optimal Bit Manipulation by Iterating Bits
This is the most efficient approach in terms of space. Instead of using an intermediate data structure to store counts, we iterate through each bit position from 0 to 30. For each bit position, we perform a full pass over the input array to count how many numbers have that bit set. If the count meets the `k` threshold, we set the corresponding bit in our result. This approach builds the result bit by bit with minimal memory overhead.
**Time:** O(N * B), where N is the length of `nums` and B is the number of bits (31). We have a nested loop structure. The outer loop runs B times, and the inner loop runs N times. · **Space:** O(1). We only use a few variables (`result`, `i`, `count`, `num`) to store intermediate values. The space required does not depend on the size of the input, making it the most space-efficient solution.
**Pros:** Most space-efficient solution with O(1) complexity.; Clear and direct implementation of the problem definition.; Efficient time complexity.
**Cons:** The memory access pattern (iterating through the whole `nums` array for each bit) might be slightly less cache-friendly than the count array approach, but this is a micro-optimization and unlikely to be significant given the problem constraints.
### Explanation
This approach refines the bit manipulation technique by changing the order of iteration. Instead of processing number by number, we process bit by bit. For each bit position from 0 to 30, we iterate through the entire `nums` array to count how many numbers have this specific bit set. If the count is sufficient (at least `k`), we immediately set that bit in our result. This avoids the need for an auxiliary array to store all bit counts simultaneously, making it the most space-efficient solution.

```java
class Solution {
    public int findKOr(int[] nums, int k) {
        int result = 0;
        // Iterate over each bit position from 0 to 30
        for (int i = 0; i < 31; i++) {
            int count = 0;
            // For each bit, count how many numbers have it set
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            // If the count is at least k, set the i-th bit in the result
            if (count >= k) {
                result |= (1 << i);
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an integer `result = 0`.
*   Iterate through each bit position `i` from 0 to 30.
*   For each bit `i`, initialize a temporary `count = 0`.
*   Iterate through each `num` in the `nums` array.
*   Check if the `i`-th bit is set in `num` and if so, increment `count`.
*   After iterating through all numbers, if `count >= k`, set the `i`-th bit in the `result`.
*   After iterating through all 31 bit positions, return `result`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int FindKOr(int[] nums, int k) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            foreach(int x in nums) {
                cnt += (x >> i & 1);
            }
            if (cnt >= k) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
}
```

### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def findKOr(self, nums: List[int], k: int) -> int: ans = 0 for i in range(32): cnt = sum(x >> i & 1 for x in nums) if cnt >= k: ans |= 1 << i return ans

```