Dada una array arr[] que consta de N enteros positivos, la tarea es modificar cada elemento de la array invirtiendo su representación binaria y contar la cantidad de elementos en la array modificada que también estaban presentes en la array original.
Ejemplos:
Entrada : arr[] = {2, 4, 5, 20, 16}
Salida: 2
Explicación:
2 -> (10) 2 -> (1) 2 -> 1 es decir, no está presente en la array original
4 -> (100 ) 2 -> (1 ) 2 -> 1 ie no presente en el arreglo original
5 -> (101 ) 2 -> (101 ) 2 -> 5 ie presente en el arreglo original
20 -> (10100) 2 -> ( 101) 2 -> 5, es decir, presente en la array original
16 -> (10000) 2 -> (1) 2 -> 1, es decir, no presente en la array originalEntrada: arr[] = {1, 30, 3, 8, 12}
Salida: 4
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos count , para almacenar el conteo requerido, un vector , digamos V , para almacenar los bits invertidos de cada elemento de la array y un Map para almacenar los elementos de la array en la array original.
- Recorra la array dada arr[] y realice los siguientes pasos:
- Almacene el número formado al invertir cada bit de representación binaria del elemento arr[i] en el vector V .
- Marca la presencia del elemento actual arr[i] en el Mapa .
- Atraviese el vector V , y si algún elemento presente en el vector también está presente en el Mapa , incremente la cuenta en 1 .
- Después de completar los pasos anteriores, imprima el valor del conteo como resultado.
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 reverse the binary
// representation of a number
int findReverse(int N)
{
int rev = 0;
// Traverse bits of N
// from the right
while (N > 0) {
// Bitwise left
// shift 'rev' by 1
rev <<= 1;
// If current bit is '1'
if (N & 1 == 1)
rev ^= 1;
// Bitwise right
// shift N by 1
N >>= 1;
}
// Required number
return rev;
}
// Function to count elements from the
// original array that are also present
// in the array formed by reversing the
// binary representation of each element
void countElements(int arr[], int N)
{
// Stores the reversed num
vector<int> ans;
// Iterate from [0, N]
for (int i = 0; i < N; i++) {
ans.push_back(findReverse(arr[i]));
}
// Stores the presence of integer
unordered_map<int, int> cnt;
for (int i = 0; i < N; i++) {
cnt[arr[i]] = 1;
}
// Stores count of elements
// present in original array
int count = 0;
// Traverse the array
for (auto i : ans) {
// If current number is present
if (cnt[i])
count++;
}
// Print the answer
cout << count << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 30, 3, 8, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
countElements(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to reverse the binary
// representation of a number
static int findReverse(int N)
{
int rev = 0;
// Traverse bits of N
// from the right
while (N > 0)
{
// Bitwise left
// shift 'rev' by 1
rev <<= 1;
// If current bit is '1'
if ((N & 1) == 1)
rev ^= 1;
// Bitwise right
// shift N by 1
N >>= 1;
}
// Required number
return rev;
}
// Function to count elements from the
// original array that are also present
// in the array formed by reversing the
// binary representation of each element
static void countElements(int arr[], int N)
{
// Stores the reversed num
Vector<Integer> ans = new Vector<Integer>();
// Iterate from [0, N]
for (int i = 0; i < N; i++)
{
ans.add(findReverse(arr[i]));
}
// Stores the presence of integer
HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++)
{
cnt.put(arr[i], 1);
}
// Stores count of elements
// present in original array
int count = 0;
// Traverse the array
for(Integer i : ans) {
// If current number is present
if (cnt.containsKey(i))
count++;
}
// Print the answer
System.out.println(count);
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 30, 3, 8, 12 };
int N = arr.length;
countElements(arr, N);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python 3 program for the above approach
# Function to reverse the binary
# representation of a number
def findReverse(N):
rev = 0
# Traverse bits of N
# from the right
while (N > 0):
# Bitwise left
# shift 'rev' by 1
rev <<= 1
# If current bit is '1'
if (N & 1 == 1):
rev ^= 1
# Bitwise right
# shift N by 1
N >>= 1
# Required number
return rev
# Function to count elements from the
# original array that are also present
# in the array formed by reversing the
# binary representation of each element
def countElements(arr, N):
# Stores the reversed num
ans = []
# Iterate from [0, N]
for i in range(N):
ans.append(findReverse(arr[i]))
# Stores the presence of integer
cnt = {}
for i in range(N):
cnt[arr[i]] = 1
# Stores count of elements
# present in original array
count = 0
# Traverse the array
for i in ans:
# If current number is present
if (i in cnt):
count += 1
# Print the answer
print(count)
# Driver Code
if __name__ == '__main__':
arr = [1, 30, 3, 8, 12]
N = len(arr)
countElements(arr, N)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to reverse the binary
// representation of a number
static int findReverse(int N)
{
int rev = 0;
// Traverse bits of N
// from the right
while (N > 0) {
// Bitwise left
// shift 'rev' by 1
rev <<= 1;
// If current bit is '1'
if ((N & 1) == 1)
rev ^= 1;
// Bitwise right
// shift N by 1
N >>= 1;
}
// Required number
return rev;
}
// Function to count elements from the
// original array that are also present
// in the array formed by reversing the
// binary representation of each element
static void countElements(int[] arr, int N)
{
// Stores the reversed num
List<int> ans = new List<int>();
// Iterate from [0, N]
for (int i = 0; i < N; i++) {
ans.Add(findReverse(arr[i]));
}
// Stores the presence of integer
Dictionary<int, int> cnt
= new Dictionary<int, int>();
for (int i = 0; i < N; i++) {
cnt[arr[i]] = 1;
}
// Stores count of elements
// present in original array
int count = 0;
// Traverse the array
foreach(int i in ans)
{
// If current number is present
if (cnt.ContainsKey(i))
count++;
}
// Print the answer
Console.WriteLine(count);
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 30, 3, 8, 12 };
int N = arr.Length;
countElements(arr, N);
}
}
// This code is contributed by chitranayal.
Javascript
<script>
// Js program for the above approach
// Function to reverse the binary
// representation of a number
function findReverse(N) {
let rev = 0;
// Traverse bits of N
// from the right
while (N > 0) {
// Bitwise left
// shift 'rev' by 1
rev <<= 1;
// If current bit is '1'
if (N & 1 == 1)
rev ^= 1;
// Bitwise right
// shift N by 1
N >>= 1;
}
// Required number
return rev;
}
// Function to count elements from the
// original array that are also present
// in the array formed by reversing the
// binary representation of each element
function countElements( arr, N)
{
// Stores the reversed num
let ans=[];
// Iterate from [0, N]
for (let i = 0; i < N; i++) {
ans.push(findReverse(arr[i]));
}
// Stores the presence of integer
let cnt = new Map();
for (let i = 0; i < N; i++) {
cnt[arr[i]] = 1;
}
// Stores count of elements
// present in original array
let count = 0;
// Traverse the array
for (let i = 0;i<ans.length;i++) {
// If current number is present
if (cnt[ans[i]])
count++;
}
// Print the answer
document.write( count,'<br>');
}
// Driver Code
let arr = [ 1, 30, 3, 8, 12 ];
let N = arr.length;
countElements(arr, N);
</script>
Producción:
4
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(N), ya que estamos usando espacio extra para el mapa cnt.
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA