Encuentre el rango más largo de los números en el rango [1, N] que tienen AND bit a bit positivo

Dado un número N , la tarea es encontrar el rango más largo de enteros [L, R] tal que 1 ≤ L ≤ R ≤ N y el AND bit a bit de todos los números en ese rango sea positivo .

Ejemplos:

Entrada: N = 7
Salida: 4 7
Explicación: Comprobar y de 1 a 7
Operaciones AND bit a bit:
de 1 a 7 es 0 
de 2 a 7 es 0
de 3 a 7 es 0
de 4 a 7 es 4
Por lo tanto, el rango máximo viene fuera de L = 4 a R = 7. 

Entrada: K = 16
Salida: 8 15

Enfoque: El problema se puede resolver con base en la siguiente observación matemática. Si 2 ^K es el exponente más cercano de 2 mayor que N entonces el rango máximo será cualquiera de los dos:

• De 2 ^{(K – 2)} a (2 ^{(K – 1)} – 1) [ambos valores inclusive] o,
• De 2 ^{(K – 1)} a N

Porque estos rangos confirman que todos los números en el rango tendrán el conjunto de bits más significativo para todos ellos. Si los rangos varían para potencias de 2, entonces el AND bit a bit del rango se convertirá en 0.

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the closest exponent of 2
// which is greater than K
int minpoweroftwo(int K)
{
    int count = 0;
    while (K > 0) {
        count++;
        K = K >> 1;
    }
    return count;
}
 
// Function to find the longest range
void findlongestrange(int N)
{
 
    int K = minpoweroftwo(N);
    int y = N + 1 - pow(2, K - 1);
    int z = (pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z) {
        cout << pow(2, K - 1) << " " << N;
    }
    else {
        cout << pow(2, K - 2) << " "
            << pow(2, K - 1) - 1;
    }
}
 
// Driver code
int main()
{
    int N = 16;
    findlongestrange(N);
    return 0;
}

// C code to implement above approach
#include <math.h>
#include <stdio.h>
 
// Function to find the closest exponent of 2
// which is greater than K
int minpoweroftwo(int K)
{
    int count = 0;
    while (K > 0) {
        count++;
        K = K >> 1;
    }
    return count;
}
 
// Function to find the longest range
void findlongestrange(int N)
{
 
    int K = minpoweroftwo(N);
    int y = N + 1 - pow(2, K - 1);
    int z = (pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z) {
        printf("%d %d", (int)pow(2, K - 1), N);
    }
    else {
        printf("%d %d", (int)pow(2, K - 2),
               (int)pow(2, K - 1)-1);
    }
}
 
// Driver code
int main()
{
    int N = 16;
    findlongestrange(N);
    return 0;
}

// Java code to implement above approach
 
class GFG {
 
    // Function to find the closest exponent of 2
    // which is greater than K
    static int minpoweroftwo(int K) {
        int count = 0;
        while (K > 0) {
            count++;
            K = K >> 1;
        }
        return count;
    }
 
    // Function to find the longest range
    static void findlongestrange(int N) {
 
        int K = minpoweroftwo(N);
        int y = (int) (N + 1 - Math.pow(2, K - 1));
        int z = (int) (Math.pow(2, K - 1) - Math.pow(2, K - 2));
 
        if (y >= z) {
            System.out.println(Math.pow(2, K - 1) + " " + N);
        } else {
            System.out.print((int) Math.pow(2, K - 2));
            System.out.print(" ");
            System.out.print((int) Math.pow(2, K - 1) - 1);
        }
    }
 
    // Driver code
    public static void main(String args[]) {
        int N = 16;
        findlongestrange(N);
    }
}
 
// This code is contributed by gfgking.

# Python code to implement above approach
 
# Function to find the closest exponent of 2
# which is greater than K
def minpoweroftwo(K):
    count = 0;
    while (K > 0):
        count += 1;
        K = K >> 1;
 
    return count;
 
# Function to find the longest range
def findlongestrange(N):
    K = minpoweroftwo(N);
    y = int(N + 1 - pow(2, K - 1));
    z = int(pow(2, K - 1) - pow(2, K - 2));
 
    if (y >= z):
        print(pow(2, K - 1) , " " , N);
    else:
        print(pow(2, K - 2));
        print(" ");
        print(pow(2, K - 1) - 1);
 
# Driver code
if __name__ == '__main__':
    N = 16;
    findlongestrange(N);
 
# This code is contributed by 29AjayKumar

// C# code to implement above approach
using System;
class GFG {
 
  // Function to find the closest exponent of 2
  // which is greater than K
  static int minpoweroftwo(int K)
  {
    int count = 0;
    while (K > 0) {
      count++;
      K = K >> 1;
    }
    return count;
  }
 
  // Function to find the longest range
  static void findlongestrange(int N)
  {
 
    int K = minpoweroftwo(N);
    int y = (int)(N + 1 - Math.Pow(2, K - 1));
    int z = (int)(Math.Pow(2, K - 1)
                  - Math.Pow(2, K - 2));
 
    if (y >= z) {
      Console.Write(Math.Pow(2, K - 1) + " " + N);
    }
    else {
      Console.Write((int)Math.Pow(2, K - 2));
      Console.Write(" ");
      Console.Write((int)Math.Pow(2, K - 1) - 1);
    }
  }
 
  // Driver code
  public static void Main()
  {
    int N = 16;
    findlongestrange(N);
  }
}
 
// This code is contributed by ukasp.

<script>
        // JavaScript code for the above approach
 
        // Function to find the closest exponent of 2
        // which is greater than K
        function minpoweroftwo(K) {
            let count = 0;
            while (K > 0) {
                count++;
                K = K >> 1;
            }
            return count;
        }
 
        // Function to find the longest range
        function findlongestrange(N)
        {
            let K = minpoweroftwo(N);
            let y = N + 1 - Math.pow(2, K - 1);
            let z = (Math.pow(2, K - 1) - Math.pow(2, K - 2));
 
            if (y >= z) {
                document.write(Math.pow(2, K - 1) + " " + N);
            }
            else {
                document.write(Math.pow(2, K - 2) + " "
                    + (Math.pow(2, K - 1) - 1));
            }
        }
 
        // Driver code
        let N = 16;
        findlongestrange(N);
 
  // This code is contributed by Potta Lokesh
    </script>

8 15

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