Dada una array arr[] que consiste en N y un entero K , la tarea es imprimir los elementos de arr[] cuyo bit establecido más a la derecha está en la misma posición que el bit establecido más a la derecha en K .
Ejemplos:
Entrada: arr[] = { 3, 4, 6, 7, 9, 12, 15 }, K = 7
Salida: { 3, 7, 9, 15 }
Explicación:
La representación binaria de K (= 7 ) es 0111 .
El bit establecido más a la derecha en 7 está en la posición 1.
Por lo tanto, todos los elementos impares de la array tendrán el bit establecido más a la derecha en la posición 1.Entrada: arr[] = { 1, 2, 3, 4, 5 }, K = 3
Salida: {1, 3, 5}
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos mask , para almacenar la máscara de K .
- Inicialice una variable, digamos pos , para almacenar la posición del bit establecido más a la derecha en K .
- Calcule el AND bit a bit de la máscara y K , es decir , pos = (máscara y K)
- Recorra la array arr[] y para cada elemento de la array:
- Si máscara & arr[i] == pos: Imprimir arr[i].
- De lo contrario, continúa .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3 7 9 15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aadityapburujwale y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA