2917. Find the K-or of an Array

Easy
Leetcode Link

Problem Description

In this problem, we're given an array of integers called nums and an integer k. We need to compute the K-or of nums. The K-or is a special value that is determined by looking at each bit position across all numbers in nums. For each bit position i, if at least k numbers in nums have a 1 in the ith bit position, then the ith bit of the K-or will also be 1. Otherwise, it will be 0. The K-or of nums is the combined result of checking this condition for each bit position from 0 to 31 (since we are dealing with 32-bit integers). This problem is essentially about understanding and manipulating binary representations of integers.

Intuition

To understand the solution, we need to grasp the concept of bitwise operations. Specifically, we will be using bitwise AND (&) and bitwise OR (|). A bitwise AND between two bits results in 1 if both bits are 1, otherwise it's 0. A bitwise OR between two bits results in 1 if at least one of the bits is 1.

To find the K-or of nums, we follow these steps:

  • We initialize our answer variable ans to 0. This will hold the final K-or value.
  • We iterate over each bit position i from 0 to 31 (since the problem states that nums is an array of non-negative integers, and non-negative integers are represented by 32-bit binary numbers).
  • For each bit position i, we count how many numbers in nums have the ith bit set to 1. We do this by right-shifting (>>) each number in nums by i positions, thus bringing the ith bit to the rightmost position. We then perform a bitwise AND with 1 (which has only the rightmost bit set to 1). This gives us the value of the ith bit. Summing up these values across all numbers in nums gives us the total count of numbers with ith bit set, cnt.
  • If cnt is greater than or equal to k, then we should have the ith bit of ans set to 1. To achieve this, we use the bitwise OR operation to set the ith bit of ans. We create a value with only the ith bit set (1 << i) and OR it with ans.
  • After checking all bit positions, ans will be the K-or of nums, which we return.

This approach works as it builds up the final K-or one bit position at a time, using bitwise operations to precisely control and tally the bits as per the problem's requirements.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A heap is a ...?

Solution Approach

The implementation of the solution follows a straightforward approach hinging on the concept of bitwise operations.

  • The algorithm employs a for loop to iterate through 32 possible bit positions (from 0 to 31) since we are working with non-negative integers, which in this case are 32-bit.

    For each bit position i, the algorithm performs a key operation:

    • It counts the number of elements in nums (cnt) that have the ith bit set to 1. This is achieved by iterating through each element x in nums and applying x >> i & 1.

      • x >> i shifts the bits of x right by i positions, moving the ith bit to the least significant position.
      • The & 1 operation is a bitwise AND which masks all bits other than x's least significant bit; effectively it extracts the value of the ith bit post-shift.

    • If the count cnt is greater than or equal to k, this indicates that at least k elements of nums have the ith bit set to 1, and thus we should set the ith bit in our solution ans.

    • To set the ith bit in ans, we use the operation ans |= 1 << i. 1 << i creates a number with only the ith bit set (2^i), and |= (bitwise OR assignment) combines this with the current ans.

      • If ans already has the ith bit set, |= will leave that bit set.
      • If ans does not have the ith bit set and cnt is greater than or equal to k, |= will set that bit to 1.

  • By the end of the loop, we have considered all bits from the least significant to the most significant and ans contains all the bits that met the condition (a count of at least k).

  • The algorithm then returns the accumulated result stored in ans as the K-or of nums.

There is no need for any additional data structures for this approach, which keeps the space complexity to O(1) - only counters and the answer variable. The time complexity is O(N * M), with N being the length of the input list and M being the number of bits we are checking (in this case, 32). The simplicity comes with the direct counting and bitwise manipulation for each of the bit positions. The reference to 2^i in the solution approach, wrapping it in "`", makes clear the relationship between shifting bits and powers of two which is central to understanding bitwise operations in this context.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example Walkthrough

Let's consider an example where the nums array is [3, 5, 12] and k is set to 2. The problem asks us to find the K-or of nums.

First, we examine the binary representations of each number in the array:

  • 3 in binary is 0011
  • 5 in binary is 0101
  • 12 in binary is 1100

We need to look through each bit position and count how many numbers have that bit set to 1. Then we'll check if this count is at least k (2 in our example).

Let's step through a few iterations of the process for each bit position i from 0 to 31.

  • For i = 0 (the least significant bit or LSB), we have:

    • 3 >> 0 & 1 = 1
    • 5 >> 0 & 1 = 1
    • 12 >> 0 & 1 = 0 The count cnt of numbers with the least significant bit set to 1 is 2, which is equal to k. Thus, we set the least significant bit of ans to 1. Now, ans = 0001.

  • For i = 1 (the second least significant bit), we have:

    • 3 >> 1 & 1 = 1
    • 5 >> 1 & 1 = 0
    • 12 >> 1 & 1 = 0 The count cnt is 1, which is less than k. We do not change ans. ans remains 0001.

  • For i = 2, we have:

    • 3 >> 2 & 1 = 0
    • 5 >> 2 & 1 = 1
    • 12 >> 2 & 1 = 1 The count cnt is 2, equal to k. We set the third least significant bit (2^2 position) of ans. Now, ans = 0101.

If we continue this process up to i = 31, we would see that no more bits would meet the condition of having at least k counts. This is because our numbers are quite small and do not have 1s in higher bit positions.

After completing this process for all bit positions, we conclude that the final ans equals 0101 in binary, which is 5 in decimal. This is the K-or of nums [3, 5, 12] with k = 2.

Solution Implementation

1from typing import List  # Necessary for type hinting
2
3class Solution:
4    def findKOr(self, nums: List[int], k: int) -> int:
5        # Initialize the answer to 0. The function will build up 
6        # the answer by setting bits where appropriate.
7        answer = 0
8      
9        # Loop through each bit position from 0 to 31 (inclusive)
10        # since an integer in Python has 32 bits
11        for i in range(32):
12            # Count number of integers in nums where the ith bit is set
13            count = sum(1 for x in nums if x >> i & 1)
14          
15            # If the count is greater than or equal to k, it means at least k numbers
16            # have a bit set at the ith position. Hence, set the ith bit in the answer.
17            if count >= k:
18                answer |= 1 << i
19      
20        # Return the computed answer where bits are set based on the count of set bits
21        # at every bit position in the input numbers compared to k.
22        return answer
23
1class Solution {
2
3    /**
4     * Finds an integer which has at least k 1-bits in the respective bit positions,
5     * when compared across all numbers in the given array.
6     *
7     * @param nums Array of integers.
8     * @param k Number representing the minimum count of 1-bits.
9     * @return The integer with at least k 1-bits in the corresponding bit positions.
10     */
11    public int findKOr(int[] nums, int k) {
12        // Initialize the variable to store the answer
13        int answer = 0;
14      
15        // Iterate through each bit position (0 to 31, assuming 32-bit integers)
16        for (int i = 0; i < 32; ++i) {
17            // Initialize a counter for the number of 1-bits in the current bit position
18            int count = 0;
19            // Iterate through all numbers in the array
20            for (int number : nums) {
21                // Shift the number i bits to the right and bitwise AND with 1
22                // This extracts the i-th bit and increases the count if it's 1
23                count += (number >> i) & 1;
24            }
25            // If the count is at least k, set the i-th bit of the answer to 1
26            if (count >= k) {
27                answer |= 1 << i;
28            }
29        }
30        // Return the computed answer with the required bits set to 1
31        return answer;
32    }
33}
34
1class Solution {
2public:
3    // Method to find the number where each bit position has appeared at least k times across all numbers in the vector.
4    int findKOr(vector<int>& nums, int k) {
5        int result = 0; // Initializes the result which will be returned.
6      
7        // Iterate through each bit position (0 to 31 for a 32-bit integer).
8        for (int i = 0; i < 32; ++i) {
9            int count = 0; // Count the number of times the i-th bit is set across all numbers in nums.
10          
11            // Iterate through all numbers in the vector.
12            for (int num : nums) {
13                // If the i-th bit is set in num, increment the count.
14                count += (num >> i) & 1;
15            }
16          
17            // If the i-th bit is set at least k times across all numbers, set this bit in the result.
18            if (count >= k) {
19                result |= (1 << i);
20            }
21        }
22      
23        // Return the result, where each bit represents it appeared at least k times across all numbers in nums.
24        return result;
25    }
26};
27
1function findKOr(nums: number[], k: number): number {
2    let answer = 0; // Initialize the answer which will hold the result
3  
4    // Iterate over 32 bits because we're assuming numbers are within 32-bit integer range
5    for (let bitPosition = 0; bitPosition < 32; ++bitPosition) {
6        let count = 0; // Count the number of times a bit is set at the current position
7      
8        // Iterate over the array and count the bits set at the current bit position
9        for (const num of nums) {
10            count += (num >> bitPosition) & 1;
11        }
12      
13        // If the count of set bits is greater than or equal to k, set the bit at this position in the answer
14        if (count >= k) {
15            answer |= 1 << bitPosition;
16        }
17    }
18  
19    // Return the final calculated answer
20    return answer;
21}
22
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n * 32), which simplifies to O(n) since 32 is a constant. Here, n is the length of the array nums. The time complexity assessment comes from the single loop running 32 times (once for each bit in a 32-bit integer) and the inner computation that performs a bitwise operation and a sum for all n elements in the array nums. This inner computation runs in O(n) time, and since it's nested inside a loop that runs a constant number of times, the overall time complexity remains linear with respect to the number of elements in nums.

Space Complexity

The space complexity of the provided code is O(1). This is because the storage used by the variables ans, i, and cnt does not scale with the size of the input nums; their size remains constant regardless of the number of elements in nums.

Fast Track Your Learning with Our Quick Skills Quiz:

How does merge sort divide the problem into subproblems?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫