Recuento mínimo de enteros consecutivos hasta N cuyo AND bit a bit es 0 con N

Dado un entero positivo N , la tarea es imprimir el recuento mínimo de números consecutivos menores que N de modo que el AND bit a bit de estos elementos consecutivos, incluido el entero N , sea igual a 0 .

Ejemplos:

Entrada: N = 18
Salida: 3
Explicación: 
Una forma posible es formar una secuencia de {15, 16, 17 y 18}. El AND bit a bit de los números dados es igual a 0.
Por lo tanto, se necesita un mínimo de 3 números para hacer el AND bit a bit de una secuencia de 4 elementos consecutivos, incluidos 18 a 0.

Entrada: N = 4
Salida: 1
Explicación: 
Una forma posible es formar una secuencia de {4, 3}. El AND bit a bit de los números dados es igual a 0.
Por lo tanto, se necesita un mínimo de 1 número para hacer el AND bit a bit de una secuencia de 2 elementos consecutivos, incluidos 4 a 0.

Enfoque ingenuo: el enfoque más simple es iterar hasta que N sea mayor que 0 y en cada iteración verificar si el AND bit a bit de los números hasta el momento es igual a 0 o no. De lo contrario, aumente el conteo en 1 .

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver con base en las siguientes observaciones: 

1. Para hacer que el AND bit a bit de la secuencia que incluye N sea igual a 0 , es necesario hacer que el bit MSB del número N sea igual a 0 .
2. Por lo tanto, la idea es incluir todos los enteros mayores o iguales a (2 ^MSB -1) y menores a N en la secuencia, dará la cuenta mínima.

Siga los pasos a continuación para resolver el problema:

• Encuentre el conjunto de bits más significativo del entero N y guárdelo en una variable, digamos m .
• Entonces el valor máximo más bajo que se incluirá es (2 ^m -1) .
• Finalmente, imprima el conteo como (N- (2 ^m -1)) .

A continuación se muestra la implementación del enfoque anterior:

// C++ Program for the above approach
#include <bits/stdc++.h>
using namespace std;
int decimalToBinary(int N)
{
  
    // To store the binary number
    int B_Number = 0;
    int cnt = 0;
    while (N != 0)
    {
        int rem = N % 2;
        double c = pow(10, cnt);
        B_Number += rem * c;
        N /= 2;
  
        // Count used to store exponent value
        cnt++;
    }
  
    return B_Number;
}
    // Function to count the minimum count of
    // integers such that bitwise AND of that
    // many consecutive elements is equal to 0
    int count(int N)
    {
 
        // Stores the binary
        // representation of N
        string a = to_string(decimalToBinary(N));
 
        // Stores the MSB bit
        int m = a.size() - 1;
       
        // Stores the count
        // of numbers
        int res = (N - (pow(2, m) - 1));
 
        // Return res
        return res;
 
    }
     
 
// Driver Code
int main() {
 
    // Given Input
    int N = 18;
 
    // Function Call
    cout<< count(N);
return 0;
}
 
// This code is contributed by shikhasingrajput

// Java program for the above approach
class GFG
{
   
    // Function to count the minimum count of
    // integers such that bitwise AND of that
    // many consecutive elements is equal to 0
    static int count(int N)
    {
 
        // Stores the binary
        // representation of N
        String a = Integer.toBinaryString(N);
 
        // Stores the MSB bit
        int m = a.length() - 1;
       
        // Stores the count
        // of numbers
        int res = (int) (N - (Math.pow(2, m) - 1));
 
        // Return res
        return res;
 
    }
 
    // Driver Code
    public static void main(String[] args) {
 
        // Given Input
        int N = 18;
 
        // Function Call
        System.out.println(count(N));
    }
}
 
// This code is contributed by shikhasingrajput

# Python program for the above approach
 
# Function to count the minimum count of
# integers such that bitwise AND of that
# many consecutive elements is equal to 0
 
 
def count(N):
 
    # Stores the binary
    # representation of N
    a = bin(N)
 
    # Excludes first two
    # characters "0b"
    a = a[2:]
 
    # Stores the MSB bit
    m = len(a)-1
 
    # Stores the count
    # of numbers
    res = N - (2**m-1)
 
    # Return res
    return res
 
 
# Driver Code
# Given Input
N = 18
 
# Function Call
print(count(N))

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
   
    // Function to count the minimum count of
    // integers such that bitwise AND of that
    // many consecutive elements is equal to 0
    static int count(int N)
    {
 
        // Stores the binary
        // representation of N
        String a = Convert.ToString(N, 2);
 
        // Stores the MSB bit
        int m = a.Length - 1;
       
        // Stores the count
        // of numbers
        int res = (int) (N - (Math.Pow(2, m) - 1));
 
        // Return res
        return res;
 
    }
 
    // Driver Code
    public static void Main(String[] args) {
 
        // Given Input
        int N = 18;
 
        // Function Call
        Console.WriteLine(count(N));
    }
}
 
// This code is contributed by umadevi9616

<script>
// javascript program for the above approach
 
    // Function to count the minimum count of
    // integers such that bitwise AND of that
    // many consecutive elements is equal to 0
    function count(N)
    {
 
        // Stores the binary
        // representation of N
        var a = N.toString(2);
 
        // Stores the MSB bit
        var m = a.length - 1;
       
        // Stores the count
        // of numbers
        var res = N - (Math.pow(2, m) - 1);
 
        // Return res
        return res;
 
    }
 
    // Driver Code
     
        // Given Input
        var N = 18;
 
        // Function Call
        document.write(count(N));
 
 
// This code is contributed by shikhasingrajput
</script>

3

Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)