Dadas N strings que representan todos los enteros de 0 a N en formato binario, excepto cualquiera. La tarea es encontrar el número que falta. La entrada consta de una array de strings donde los elementos de la array se representan en formato binario.
Ejemplos:
Entrada: arr[] = {“0000”, “0001”, “0010”, “0100”}
Salida: 3
Entrada: arr[] = {“0000”, “0001”, “0010”, “0011”, “ 0100”, “0110”, “0111”, “1000”}
Salida : 5
Acercarse:
- Se puede observar un desequilibrio de 1 y 0 en los bits menos significativos de los números en los N enteros dados. Dado que falta un número, falta un 0 o un 1 del LSB. Si el número que falta tiene LSB = 0, la cuenta (1) será mayor que igual a la cuenta (0). Si el LSB del número que falta es 1, entonces la cuenta (1) es menor que la cuenta (0).
- Desde el paso 1 se puede determinar fácilmente el LSB del número faltante.
- Una vez determinado, descartar todos los números que tengan LSB diferente al del número que falta, es decir, si el número que falta tiene LSB = 0, entonces descartar todos los números con LSB = 1 y viceversa.
- Continúe el proceso desde el paso 1 nuevamente y repítalo para el siguiente LSB.
- Continúe con el proceso anterior hasta que se atraviesen todos los bits.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the missing integer
// in N numbers when N bits are given
#include <bits/stdc++.h>
using namespace std;
class BitInteger {
private:
bool* bits;
public:
static const int INTEGER_SIZE = 32;
BitInteger()
{
bits = new bool[INTEGER_SIZE];
}
// Constructor to convert an integer
// variable into binary format
BitInteger(int value)
{
bits = new bool[INTEGER_SIZE];
for (int j = 0; j < INTEGER_SIZE; j++) {
// The if statement will shift the
// original value j times.
// So that appropriate (INTEGER_SIZE - 1 -j)th
// bits will be either 0/1.
// (INTEGER_SIZE - 1 -j)th bit for all
// j = 0 to INTEGER_SIZE-1 corresponds
// to LSB to MSB respectively.
if (((value >> j) & 1) == 1)
bits[INTEGER_SIZE - 1 - j] = true;
else
bits[INTEGER_SIZE - 1 - j] = false;
}
}
// Constructor to convert a
// string into binary format.
BitInteger(string str)
{
int len = str.length();
int x = INTEGER_SIZE - len;
bits = new bool[INTEGER_SIZE];
// If len = 4. Then x = 32 - 4 = 28.
// Hence iterate from
// bit 28 to bit 32 and just
// replicate the input string.
int i = 0;
for (int j = x; j <= INTEGER_SIZE && i < len; j++, i++) {
if (str[i] == '1')
bits[j] = true;
else
bits[j] = false;
}
}
// this function fetches the kth bit
int fetch(int k)
{
if (bits[k])
return 1;
return 0;
}
// this function will set a value
// of bit indicated by k to given bitValue
void set(int k, int bitValue)
{
if (bitValue == 0)
bits[k] = false;
else
bits[k] = true;
}
// convert binary representation to integer
int toInt()
{
int n = 0;
for (int i = 0; i < INTEGER_SIZE; i++) {
n = n << 1;
if (bits[i])
n = n | 1;
}
return n;
}
};
// Function to find the missing number
int findMissingFunc(list<BitInteger>& myList, int column)
{
// This means that we have processed
// the entire 32 bit binary number.
if (column < 0)
return 0;
list<BitInteger> oddIndices;
list<BitInteger> evenIndices;
for (BitInteger t : myList) {
// Initially column = LSB. So
// if LSB of the given number is 0,
// then the number is even and
// hence we add it to evenIndices list.
// else if LSB = 0 then add it to oddIndices list.
if (t.fetch(column) == 0)
evenIndices.push_back(t);
else
oddIndices.push_back(t);
}
// Step 1 and Step 2 of the algorithm.
// Here we determine the LSB bit of missing number.
if (oddIndices.size() >= evenIndices.size())
// LSB of the missing number is 0.
// Hence it is an even number.
// Step 3 and 4 of the algorithm
// (discarding all odd numbers)
return (findMissingFunc(evenIndices, column - 1)) << 1 | 0;
else
// LSB of the missing number is 1.
// Hence it is an odd number.
// Step 3 and 4 of the algorithm
// (discarding all even numbers)
return (findMissingFunc(oddIndices, column - 1)) << 1 | 1;
}
// Function to return the missing integer
int findMissing(list<BitInteger>& myList)
{
// Initial call is with given array and LSB.
return findMissingFunc(myList, BitInteger::INTEGER_SIZE - 1);
}
// Driver Code.
int main()
{
// a corresponds to the input array which
// is a list of binary numbers
list<BitInteger> a = { BitInteger("0000"), BitInteger("0001"),
BitInteger("0010"), BitInteger("0100"),
BitInteger("0101") };
int missing1 = findMissing(a);
cout << missing1 << "\n";
return 0;
}
Java
// Java program to find the missing integer
// in N numbers when N bits are given
import java.util.*;
class BitInteger {
boolean[] bits;
public static int INTEGER_SIZE = 32;
public BitInteger()
{
bits = new boolean[INTEGER_SIZE];
}
// Constructor to convert an integer
// variable into binary format
public BitInteger(int value)
{
bits = new boolean[INTEGER_SIZE];
for (int j = 0; j < INTEGER_SIZE; j++) {
// The if statement will shift the
// original value j times.
// So that appropriate (INTEGER_SIZE - 1 -j)th
// bits will be either 0/1.
// (INTEGER_SIZE - 1 -j)th bit for all
// j = 0 to INTEGER_SIZE-1 corresponds
// to LSB to MSB respectively.
if (((value >> j) & 1) == 1)
bits[INTEGER_SIZE - 1 - j] = true;
else
bits[INTEGER_SIZE - 1 - j] = false;
}
}
// Constructor to convert a
// string into binary format.
public BitInteger(String str)
{
int len = str.length();
int x = INTEGER_SIZE - len;
bits = new boolean[INTEGER_SIZE];
// If len = 4. Then x = 32 - 4 = 28.
// Hence iterate from
// bit 28 to bit 32 and just
// replicate the input string.
int i = 0;
for (int j = x; j <= INTEGER_SIZE && i < len;
j++, i++) {
if (str.charAt(i) == '1')
bits[j] = true;
else
bits[j] = false;
}
}
// this function fetches the kth bit
int fetch(int k)
{
if (bits[k])
return 1;
return 0;
}
// this function will set a value
// of bit indicated by k to given bitValue
void set(int k, int bitValue)
{
if (bitValue == 0)
bits[k] = false;
else
bits[k] = true;
}
// convert binary representation to integer
int toInt()
{
int n = 0;
for (int i = 0; i < INTEGER_SIZE; i++) {
n = n << 1;
if (bits[i])
n = n | 1;
}
return n;
}
};
class GFG {
// Function to find the missing number
static int findMissingFunc(ArrayList<BitInteger> myList,
int column)
{
// This means that we have processed
// the entire 32 bit binary number.
if (column < 0)
return 0;
ArrayList<BitInteger> oddIndices
= new ArrayList<BitInteger>();
ArrayList<BitInteger> evenIndices
= new ArrayList<BitInteger>();
for (BitInteger t : myList) {
// Initially column = LSB. So
// if LSB of the given number is 0,
// then the number is even and
// hence we add it to evenIndices list.
// else if LSB = 0 then add it to oddIndices
// list.
if (t.fetch(column) == 0)
evenIndices.add(t);
else
oddIndices.add(t);
}
// Step 1 and Step 2 of the algorithm.
// Here we determine the LSB bit of missing number.
if (oddIndices.size() >= evenIndices.size())
// LSB of the missing number is 0.
// Hence it is an even number.
// Step 3 and 4 of the algorithm
// (discarding all odd numbers)
return (findMissingFunc(evenIndices,
column - 1))
<< 1
| 0;
else
// LSB of the missing number is 1.
// Hence it is an odd number.
// Step 3 and 4 of the algorithm
// (discarding all even numbers)
return (findMissingFunc(oddIndices, column - 1))
<< 1
| 1;
}
// Function to return the missing integer
static int findMissing(ArrayList<BitInteger> myList)
{
// Initial call is with given array and LSB.
return findMissingFunc(myList,
BitInteger.INTEGER_SIZE - 1);
}
public static void main(String[] args)
{
// a corresponds to the input array which
// is a list of binary numbers
ArrayList<BitInteger> a
= new ArrayList<BitInteger>();
a.add(new BitInteger("0000"));
a.add(new BitInteger("0001"));
a.add(new BitInteger("0010"));
a.add(new BitInteger("0100"));
a.add(new BitInteger("0101"));
int missing1 = findMissing(a);
System.out.println(missing1);
}
}
// This code is contributed by phasing17
C#
// C# program to find the missing integer
// in N numbers when N bits are given
using System;
using System.Collections.Generic;
class BitInteger {
bool[] bits;
public static int INTEGER_SIZE = 32;
public BitInteger() { bits = new bool[INTEGER_SIZE]; }
// Constructor to convert an integer
// variable into binary format
public BitInteger(int value)
{
bits = new bool[INTEGER_SIZE];
for (int j = 0; j < INTEGER_SIZE; j++) {
// The if statement will shift the
// original value j times.
// So that appropriate (INTEGER_SIZE - 1 -j)th
// bits will be either 0/1.
// (INTEGER_SIZE - 1 -j)th bit for all
// j = 0 to INTEGER_SIZE-1 corresponds
// to LSB to MSB respectively.
if (((value >> j) & 1) == 1)
bits[INTEGER_SIZE - 1 - j] = true;
else
bits[INTEGER_SIZE - 1 - j] = false;
}
}
// Constructor to convert a
// string into binary format.
public BitInteger(string str)
{
int len = str.Length;
int x = INTEGER_SIZE - len;
bits = new bool[INTEGER_SIZE];
// If len = 4. Then x = 32 - 4 = 28.
// Hence iterate from
// bit 28 to bit 32 and just
// replicate the input string.
int i = 0;
for (int j = x; j <= INTEGER_SIZE && i < len;
j++, i++) {
if (str[i] == '1')
bits[j] = true;
else
bits[j] = false;
}
}
// this function fetches the kth bit
public int fetch(int k)
{
if (bits[k])
return 1;
return 0;
}
// this function will set a value
// of bit indicated by k to given bitValue
public void set(int k, int bitValue)
{
if (bitValue == 0)
bits[k] = false;
else
bits[k] = true;
}
// convert binary representation to integer
public int toInt()
{
int n = 0;
for (int i = 0; i < INTEGER_SIZE; i++) {
n = n << 1;
if (bits[i])
n = n | 1;
}
return n;
}
};
class GFG {
// Function to find the missing number
static int findMissingFunc(List<BitInteger> myList,
int column)
{
// This means that we have processed
// the entire 32 bit binary number.
if (column < 0)
return 0;
List<BitInteger> oddIndices
= new List<BitInteger>();
List<BitInteger> evenIndices
= new List<BitInteger>();
foreach(BitInteger t in myList)
{
// Initially column = LSB. So
// if LSB of the given number is 0,
// then the number is even and
// hence we add it to evenIndices list.
// else if LSB = 0 then add it to oddIndices
// list.
if (t.fetch(column) == 0)
evenIndices.Add(t);
else
oddIndices.Add(t);
}
// Step 1 and Step 2 of the algorithm.
// Here we determine the LSB bit of missing number.
if (oddIndices.Count >= evenIndices.Count)
// LSB of the missing number is 0.
// Hence it is an even number.
// Step 3 and 4 of the algorithm
// (discarding all odd numbers)
return (findMissingFunc(evenIndices,
column - 1))
<< 1
| 0;
else
// LSB of the missing number is 1.
// Hence it is an odd number.
// Step 3 and 4 of the algorithm
// (discarding all even numbers)
return (findMissingFunc(oddIndices, column - 1))
<< 1
| 1;
}
// Function to return the missing integer
static int findMissing(List<BitInteger> myList)
{
// Initial call is with given array and LSB.
return findMissingFunc(myList,
BitInteger.INTEGER_SIZE - 1);
}
public static void Main(string[] args)
{
// a corresponds to the input array which
// is a list of binary numbers
List<BitInteger> a = new List<BitInteger>();
a.Add(new BitInteger("0000"));
a.Add(new BitInteger("0001"));
a.Add(new BitInteger("0010"));
a.Add(new BitInteger("0100"));
a.Add(new BitInteger("0101"));
int missing1 = findMissing(a);
Console.WriteLine(missing1);
}
}
// This code is contributed by phasing17
Producción:
3
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por Yatharth Sant y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA