Dados dos enteros x y n , la tarea es buscar el primer flujo consecutivo de 1 (en la representación binaria de 32 bits de x ) que sea mayor o igual que n en longitud y devolver su posición. Si no existe tal string, devuelva -1.
Ejemplos:
Entrada: x = 35, n = 2
Salida: 31 La
representación binaria de 35 es 00000000000000000000000000100011 y dos 1 consecutivos están presentes en la posición 31.
Entrada: x = 32, n = 3
Salida: -1
32 = 000000000000000000000000000010000 en binario y no lo hace tener una substring de 3 1 consecutivos.
Enfoque: use la operación bit a bit para calcular el número. de ceros iniciales en el número y luego úselo para encontrar la posición desde donde necesitamos comenzar a buscar 1 consecutivos. Omita la búsqueda de ceros iniciales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the
// number of leading zeros
int countLeadingZeros(int x)
{
unsigned y;
int n;
n = 32;
y = x >> 16;
if (y != 0) {
n = n - 16;
x = y;
}
y = x >> 8;
if (y != 0) {
n = n - 8;
x = y;
}
y = x >> 4;
if (y != 0) {
n = n - 4;
x = y;
}
y = x >> 2;
if (y != 0) {
n = n - 2;
x = y;
}
y = x >> 1;
if (y != 0)
return n - 2;
return n - x;
}
// Function to find the string
// of n consecutive 1's
int FindStringof1s(unsigned x, int n)
{
int k, p;
// Initialize position to return.
p = 0;
while (x != 0) {
// Skip leading 0's
k = countLeadingZeros(x);
x = x << k;
// Set position after leading 0's
p = p + k;
// Count first group of 1's.
k = countLeadingZeros(~x);
// If length of consecutive 1's
// is greater than or equal to n
if (k >= n)
return p + 1;
// Not enough 1's
// skip over to next group
x = x << k;
// Update the position
p = p + k;
}
// if no string is found
return -1;
}
// Driver code
int main()
{
int x = 35;
int n = 2;
cout << FindStringof1s(x, n);
}
Java
// Java implementation of above approach
import java.io.*;
class GFG {
// Function to count the
// number of leading zeros
static int countLeadingZeros(int x)
{
int y;
int n;
n = 32;
y = x >> 16;
if (y != 0) {
n = n - 16;
x = y;
}
y = x >> 8;
if (y != 0) {
n = n - 8;
x = y;
}
y = x >> 4;
if (y != 0) {
n = n - 4;
x = y;
}
y = x >> 2;
if (y != 0) {
n = n - 2;
x = y;
}
y = x >> 1;
if (y != 0)
return n - 2;
return n - x;
}
// Function to find the string
// of n consecutive 1's
static int FindStringof1s(int x, int n)
{
int k, p;
// Initialize position to return.
p = 0;
while (x != 0) {
// Skip leading 0's
k = countLeadingZeros(x);
x = x << k;
// Set position after leading 0's
p = p + k;
// Count first group of 1's.
k = countLeadingZeros(~x);
// If length of consecutive 1's
// is greater than or equal to n
if (k >= n)
return p + 1;
// Not enough 1's
// skip over to next group
x = x << k;
// Update the position
p = p + k;
}
// if no string is found
return -1;
}
// Driver code
public static void main (String[] args) {
int x = 35;
int n = 2;
System.out.println(FindStringof1s(x, n));
}
}
C#
// C# implementation of above approach
using System;
public class GFG{
// Function to count the
// number of leading zeros
static int countLeadingZeros(int x)
{
int y;
int n;
n = 32;
y = x >> 16;
if (y != 0) {
n = n - 16;
x = y;
}
y = x >> 8;
if (y != 0) {
n = n - 8;
x = y;
}
y = x >> 4;
if (y != 0) {
n = n - 4;
x = y;
}
y = x >> 2;
if (y != 0) {
n = n - 2;
x = y;
}
y = x >> 1;
if (y != 0)
return n - 2;
return n - x;
}
// Function to find the string
// of n consecutive 1's
static int FindStringof1s(int x, int n)
{
int k, p;
// Initialize position to return.
p = 0;
while (x != 0) {
// Skip leading 0's
k = countLeadingZeros(x);
x = x << k;
// Set position after leading 0's
p = p + k;
// Count first group of 1's.
k = countLeadingZeros(~x);
// If length of consecutive 1's
// is greater than or equal to n
if (k >= n)
return p + 1;
// Not enough 1's
// skip over to next group
x = x << k;
// Update the position
p = p + k;
}
// if no string is found
return -1;
}
// Driver code
static public void Main (){
int x = 35;
int n = 2;
Console.WriteLine (FindStringof1s(x, n));
}
}
Javascript
<script>
// Javascript implementation of above approach
// Function to count the
// number of leading zeros
function countLeadingZeros(x) {
let y;
let n;
n = 32;
y = x >> 16;
if (y != 0) {
n = n - 16;
x = y;
}
y = x >> 8;
if (y != 0) {
n = n - 8;
x = y;
}
y = x >> 4;
if (y != 0) {
n = n - 4;
x = y;
}
y = x >> 2;
if (y != 0) {
n = n - 2;
x = y;
}
y = x >> 1;
if (y != 0)
return n - 2;
return n - x;
}
// Function to find the string
// of n consecutive 1's
function FindStringof1s(x, n) {
let k, p;
// Initialize position to return.
p = 0;
while (x != 0) {
// Skip leading 0's
k = countLeadingZeros(x);
x = x << k;
// Set position after leading 0's
p = p + k;
// Count first group of 1's.
k = countLeadingZeros(~x);
// If length of consecutive 1's
// is greater than or equal to n
if (k >= n)
return p + 1;
// Not enough 1's
// skip over to next group
x = x << k;
// Update the position
p = p + k;
}
// if no string is found
return -1;
}
// Driver code
let x = 35;
let n = 2;
document.write(FindStringof1s(x, n));
// This code is contributed by gfgking.
</script>
31
Enfoque: uso de funciones predefinidas
x se puede convertir en una string binaria utilizando métodos integrados, como bitset<32>(x).to_string() en C++ STL, bin() en Python3, Integer.toBinary() en Java. Y se puede construir una string de n 1, cuyo índice en la string binaria se puede ubicar usando funciones predefinidas como find en C++ STL, index en Python3 e indexOf() en Java.
Este enfoque se puede resumir en los siguientes pasos:
1. Forme la string binaria equivalente al número utilizando métodos integrados, como bitset<32>(x).to_string() en C++ STL, bin() en Python3, Integer.toBinary() en Java.
2. Luego, construya una string que consta de n 1, usando métodos integrados, como string (n, ‘1’) en C++ STL, ‘1’ * n en Python3 y “1”.repeat(n) en Java.
3. Luego, busque el índice de la string de n 1 en la string binaria utilizando métodos integrados como .find() en C++ STL, index() en Python3 e indexOf() en Java.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the string
// of n consecutive 1's
int FindStringof1s(unsigned x, int n)
{
// converting x to a binary string
string bin = bitset<32>(x).to_string();
// constructing a string of n 1s
string ones(n, '1');
// locating the ones string in bin
auto pos = bin.find(ones);
if (pos != string::npos)
return pos + 1;
// if no string is found
return -1;
}
// Driver code
int main()
{
int x = 35;
int n = 2;
// Function call
cout << FindStringof1s(x, n);
}
// This code is contributed by phasing17
Python3
# Python3 implementation of above approach # Function to find the string # of n consecutive 1's def FindStringof1s(x, n): # converting x to a binary string bin_ = bin(x).zfill(32) # constructing a string of n 1s ones = n * "1" # locating the ones string in bin if ones in bin_: return bin_.index(ones) + 1 # if no string is found return -1; # Driver code x = 35 n = 2 # Function call print(FindStringof1s(x, n)) # This code is contributed by phasing17
31
Complejidad de tiempo: O (logn)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Shubham__Ranjan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA