Find array elements with rightmost set bit at the position of the rightmost set bit in K

0 0 8 minutes read

Given an array arr[] consisting of N and an integer K, the task is to print the elements of arr[] whose rightmost set bit is at the same position as the rightmost set bit in K.

Examples:

Input: arr[] = { 3, 4, 6, 7, 9, 12, 15 }, K = 7
Output: { 3, 7, 9, 15 }
Explanation:
Binary representation of K (= 7) is 0111.
Rightmost set bit in 7 is at position 1.
Therefore, all odd array elements will have rightmost set bit at position 1.

Input: arr[] = { 1, 2, 3, 4, 5 }, K = 3
Output: {1, 3, 5}

Approach: Follow the steps below to solve the problem:

Initialize a variable, say mask, to store the mask of K.
Initialize a variable, say pos, to store the position of the rightmost set bit in K.
Calculate the Bitwise AND of the mask and K i.e. pos = (mask & K)
Traverse the array arr[] and for each array element:
- If mask & arr[i] == pos: Print arr[i].
- Otherwise, continue.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to find the mask for
// finding rightmost set bit in K
    int findMask(int K)
    {
        int mask = 1;
        while ((K & mask) == 0) 
        {
            mask = mask << 1;
        }
        return mask;
    }
 
    // Function to find all array elements
    // with rightmost set bit same as that in K
    void sameRightSetBitPos(
        int arr[], int N, int K)
    {
       
        // Stores mask of K
        int mask = findMask(K);
 
        // Store position of rightmost set bit
        int pos = (K & mask);
 
        // Traverse the array
        for (int i = 0; i < N; i++)
        {
 
            // Check if rightmost set bit of
            // current array element is same as
            // position of rightmost set bit in K
            if ((arr[i] & mask) == pos)
                cout << arr[i] << " ";
        }
    }
 
// Driver Code
int main()
{
    // Input
        int arr[] = { 3, 4, 6, 7, 9, 12, 15 };
        int N = sizeof(arr) / sizeof(arr[0]);
        int K = 7;
 
        // Function call to find
        // the elements having same
        // rightmost set bit as of K
        sameRightSetBitPos(arr, N, K);
 
    return 0;
}
 
// This code is contributed by susmitakundugoaldanga.

Java

// Java program for
// the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the mask for
    // finding rightmost set bit in K
    static int findMask(int K)
    {
        int mask = 1;
        while ((K & mask) == 0) {
            mask = mask << 1;
        }
        return mask;
    }
 
    // Function to find all array elements
    // with rightmost set bit same as that in K
    public static void sameRightSetBitPos(
        int[] arr, int N, int K)
    {
        // Stores mask of K
        int mask = findMask(K);
 
        // Store position of rightmost set bit
        final int pos = (K & mask);
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // Check if rightmost set bit of
            // current array element is same as
            // position of rightmost set bit in K
            if ((arr[i] & mask) == pos)
                System.out.print(arr[i] + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input
        int[] arr = { 3, 4, 6, 7, 9, 12, 15 };
        int N = arr.length;
        int K = 7;
 
        // Function call to find
        // the elements having same
        // rightmost set bit as of K
        sameRightSetBitPos(arr, N, K);
    }
}

Python3

# Python program for
# the above approach
 
# Function to find the mask for
# finding rightmost set bit in K
def findMask(K):
    mask = 1;
    while ((K & mask) == 0):
        mask = mask << 1;
 
    return mask;
 
# Function to find all array elements
# with rightmost set bit same as that in K
def sameRightSetBitPos(arr, N, K):
   
    # Stores mask of K
    mask = findMask(K);
 
    # Store position of rightmost set bit
    pos = (K & mask);
 
    # Traverse the array
    for i in range(N):
 
        # Check if rightmost set bit of
        # current array element is same as
        # position of rightmost set bit in K
        if ((arr[i] & mask) == pos):
            print(arr[i], end=" ");
 
 
# Driver Code
if __name__ == '__main__':
    # Input
    arr = [3, 4, 6, 7, 9, 12, 15];
    N = len(arr);
    K = 7;
 
    # Function call to find
    # the elements having same
    # rightmost set bit as of K
    sameRightSetBitPos(arr, N, K);
 
    # This code contributed by shikhasingrajput

C#

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to find the mask for
  // finding rightmost set bit in K
  static int findMask(int K)
  {
    int mask = 1;
    while ((K & mask) == 0) {
      mask = mask << 1;
    }
    return mask;
  }
 
  // Function to find all array elements
  // with rightmost set bit same as that in K
  public static void sameRightSetBitPos(
    int[] arr, int N, int K)
  {
    // Stores mask of K
    int mask = findMask(K);
 
    // Store position of rightmost set bit
    int pos = (K & mask);
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
      // Check if rightmost set bit of
      // current array element is same as
      // position of rightmost set bit in K
      if ((arr[i] & mask) == pos)
        Console.Write(arr[i] + " ");
    }
  }
 
 
  // Driver Code
  static public void Main ()
  {
    // Input
    int[] arr = { 3, 4, 6, 7, 9, 12, 15 };
    int N = arr.Length;
    int K = 7;
 
    // Function call to find
    // the elements having same
    // rightmost set bit as of K
    sameRightSetBitPos(arr, N, K);
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
// JavaScript program for the above approach
 
// Function to find the mask for
// finding rightmost set bit in K
    function findMask(K)
    {
        let mask = 1;
        while ((K & mask) == 0)
        {
            mask = mask << 1;
        }
        return mask;
    }
 
    // Function to find all array elements
    // with rightmost set bit same as that in K
    function sameRightSetBitPos(arr, N, K)
    {
     
        // Stores mask of K
        let mask = findMask(K);
 
        // Store position of rightmost set bit
        let pos = (K & mask);
 
        // Traverse the array
        for (let i = 0; i < N; i++)
        {
 
            // Check if rightmost set bit of
            // current array element is same as
            // position of rightmost set bit in K
            if ((arr[i] & mask) == pos)
                document.write(arr[i] + " ");
        }
    }
 
// Driver Code
 
    // Input
        let arr = [ 3, 4, 6, 7, 9, 12, 15 ];
        let N = arr.length;
        let K = 7;
 
        // Function call to find
        // the elements having same
        // rightmost set bit as of K
        sameRightSetBitPos(arr, N, K);
 
// This code is contributed by Manoj.
</script>

Output

3 7 9 15

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach#2: Using list comprehension with bitwise operations

This approach to find the position of the rightmost set bit in the given number K, and then check if the rightmost set bit in each element of the given array is at the same position as K. If it is, then the element is added to the result list.

Algorithm

1. Find the position of the rightmost set bit in K using the bitwise AND operation with its 2’s complement.
2. Initialize an empty list result to store the elements of the array that have the rightmost set bit at the same position as K.
3. Iterate through each element num in the array:
a. Check if the rightmost set bit in num is at the same position as K using the bitwise AND operation with rightmost_set_bit.
b. If the rightmost set bit is at the same position, add num to the result list.
4. Return the result list.

C++

// C++ implementation of the above approach
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> find_elements(vector<int> arr, int K)
{
    // bit in K get the position of the rightmost set
    int rightmost_set_bit = K & -K;
    vector<int> result;
    for (int num : arr) {
        // check if the rightmost set bit in num is at the
        // same position as K
        if (num & rightmost_set_bit == rightmost_set_bit) {
            // add num to the result vector
            result.push_back(num);
        }
    }
    return result;
}
 
int main()
{
    vector<int> arr = { 3, 4, 6, 7, 9, 12, 15 };
    int K = 7;
    vector<int> result = find_elements(arr, K);
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}
 
// This code is contributed by Sakshi

Java

import java.util.ArrayList;
import java.util.List;
 
public class Main {
    public static List<Integer> findElements(List<Integer> arr, int K) {
        // Bit in K to get the position of the rightmost set bit
        int rightmostSetBit = K & -K;
        List<Integer> result = new ArrayList<>();
 
        for (int num : arr) {
            // Check if the rightmost set bit in num is at the same position as K
            if ((num & rightmostSetBit) == rightmostSetBit) {
                // Add num to the result list
                result.add(num);
            }
        }
        return result;
    }
// Driver Code
    public static void main(String[] args) {
        List<Integer> arr = List.of(3, 4, 6, 7, 9, 12, 15);
        int K = 7;
        List<Integer> result = findElements(arr, K);
 
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Python3

def find_elements(arr, K):
    rightmost_set_bit = K & -K  # get the position of the rightmost set bit in K
    # check if the rightmost set bit in num is at the same position as K and add num to the result list
    return [num for num in arr if num & rightmost_set_bit == rightmost_set_bit]
 
 
arr = [3, 4, 6, 7, 9, 12, 15]
K = 7
result = find_elements(arr, K)
print(" ".join(str(num) for num in result))

C#

using System;
using System.Collections.Generic;
 
class Program
{
    static List<int> FindElements(List<int> arr, int K)
    {
        // Bit in K to get the position of the rightmost set bit
        int rightmostSetBit = K & -K;
        List<int> result = new List<int>();
 
        foreach (int num in arr)
        {
            // Check if the rightmost set bit in num is at the same position as K
            if ((num & rightmostSetBit) == rightmostSetBit)
            {
                // Add num to the result list
                result.Add(num);
            }
        }
 
        return result;
    }
 
    static void Main()
    {
        List<int> arr = new List<int> { 3, 4, 6, 7, 9, 12, 15 };
        int K = 7;
 
        List<int> result = FindElements(arr, K);
 
        foreach (int num in result)
        {
            Console.Write(num + " ");
        }
 
        Console.WriteLine();
    }
}

Javascript

// Javascript implementation of the above approach
 
function find_elements(arr, K) {
    // bit in K get the position of the rightmost set
    let rightmost_set_bit = K & -K;
    let result = [];
    for (let num of arr) {
        // check if the rightmost set bit in num is at the
        // same position as K
        if ((num & rightmost_set_bit) === rightmost_set_bit) {
            // add num to the result vector
            result.push(num);
        }
    }
    return result;
}
 
let arr = [3, 4, 6, 7, 9, 12, 15];
let K = 7;
let result = find_elements(arr, K);
for (let num of result) {
    console.log(num);
}

Output

3 7 9 15

Time complexity: O(n), where n is the length of the input array. This is because the code iterates through each element of the array once to check if the rightmost set bit is at the same position as K.

Auxiliary Space: O(m), where m is the length of the result list. In the worst case, all elements of the array could have the rightmost set bit at the same position as K, so the result list could have m elements. However, in practice, the size of the result list will likely be much smaller than the size of the input array, so the space complexity will be closer to O(1) in most cases.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!