Conjunto máximo de números de los primeros N números naturales cuyo AND bit a bit es positivo

Dado un entero positivo N , la tarea es encontrar el conjunto máximo de números de los primeros N números naturales cuyo AND bit a bit es positivo

Ejemplos:

Entrada: N = 7
Salida: 4
Explicación:
El conjunto de números de los primeros N(= 7) números naturales cuyo AND bit a bit es positivo es {4, 5, 6, 7}, que es de longitud máxima.

Entrada: N = 16
Salida: 8

Enfoque: El problema dado se puede resolver con base en la observación de que 2 ^N y (2 ^N – 1) , dan como resultado 0 . Por lo tanto, la longitud máxima del conjunto no debe incluir 2 ^N y (2 ^N – 1) en el mismo conjunto. El subarreglo máximo con un valor AND distinto de cero se puede encontrar como:

• Encuentre la potencia máxima de 2 menor o igual a N y si N es una potencia de 2 , la respuesta debe ser N/2 , por ejemplo, cuando N es 16 , el subarreglo máximo con un valor AND distinto de cero es 8 .
• De lo contrario, la respuesta es la longitud entre N y la mayor potencia de 2 menor o igual que N.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum set of
// number whose Bitwise AND is positive
int maximumSizeOfSet(int N)
{
    // Base Case
    if (N == 1)
        return 1;
 
    // Store the power of 2 less than
    // or equal to N
    int temp = 1;
    while (temp * 2 <= N) {
        temp *= 2;
    }
 
    // N is power of 2
    if (N & (N - 1) == 0)
        return N / 2;
    else
        return N - temp + 1;
}
 
// Driver Code
int main()
{
    int N = 7;
    cout << maximumSizeOfSet(N);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to find the maximum set of
// number whose Bitwise AND is positive
public static int maximumSizeOfSet(int N)
{
   
    // Base Case
    if (N == 1)
        return 1;
 
    // Store the power of 2 less than
    // or equal to N
    int temp = 1;
    while (temp * 2 <= N) {
        temp *= 2;
    }
 
    // N is power of 2
    if ((N & (N - 1)) == 0)
        return N / 2;
    else
        return N - temp + 1;
}
 
// Driver Code
public static void main(String args[])
{
    int N = 7;
    System.out.println(maximumSizeOfSet(N));
}
 
}
 
// This code is contributed by gfgking.

# python program for the above approach
 
# Function to find the maximum set of
# number whose Bitwise AND is positive
def maximumSizeOfSet(N):
 
    # Base Case
    if (N == 1):
        return 1
 
    # Store the power of 2 less than
    # or equal to N
    temp = 1
    while (temp * 2 <= N):
        temp *= 2
 
    # N is power of 2
    if (N & (N - 1) == 0):
        return N // 2
    else:
        return N - temp + 1
 
# Driver Code
if __name__ == "__main__":
 
    N = 7
    print(maximumSizeOfSet(N))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
 
public class GFG {
 
    static int maximumSizeOfSet(int N)
    {
 
        // Base Case
        if (N == 1)
            return 1;
 
        // Store the power of 2 less than
        // or equal to N
        int temp = 1;
        while (temp * 2 <= N) {
            temp *= 2;
        }
 
        // N is power of 2
        if ((N & (N - 1)) == 0)
            return N / 2;
        else
            return N - temp + 1;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 7;
 
        Console.WriteLine(maximumSizeOfSet(N));
    }
}
 
// This code is contributed by dwivediyash

<script>
    // JavaScript program for the above approach
 
    // Function to find the maximum set of
    // number whose Bitwise AND is positive
    const maximumSizeOfSet = (N) => {
        // Base Case
        if (N == 1)
            return 1;
 
        // Store the power of 2 less than
        // or equal to N
        let temp = 1;
        while (temp * 2 <= N) {
            temp *= 2;
        }
 
        // N is power of 2
        if (N & (N - 1) == 0)
            return parseInt(N / 2);
        else
            return N - temp + 1;
    }
 
    // Driver Code
    let N = 7;
    document.write(maximumSizeOfSet(N));
 
    // This code is contributed by rakeshsahni
 
</script>

4

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