Maximice el mayor número K tal que bit a bit y de K hasta que N sea 0

Dado un número entero N, la tarea es encontrar el valor máximo de K tal que N & (N-1) & (N-2) & … & (K) = 0. Aquí & representa el operador AND bit a bit .

Ejemplo:

Entrada: N = 5
Salida: 3
Explicación: El valor de la expresión 5 & 4 & 3 = 0 . cualquier valor mayor que 3 (ejemplo 4) no satisfará
nuestra condición dada

Entrada: N =17
Salida: 15

Enfoque ingenuo: el enfoque de fuerza bruta es comenzar desde N-1 y realizar una operación AND bit a bit hasta que obtengamos 0.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum value of k
// which makes bitwise AND zero.
int findMaxK(int N)
{
    // Take k = N initially
    int K = N;
 
    // Start traversing from N-1 till 0
    for (int i = N - 1; i >= 0; i--) {
        K &= i;
 
        // Whenever we get AND as 0
        // we stop and return
        if (K == 0) {
            return i;
        }
    }
    return 0;
}
 
// Driver Code
int main()
{
    int N = 5;
    cout << findMaxK(N);
}

// Java program for the above approach
 
import java.io.*;
 
class GFG {
  // Function to find maximum value of k
// which makes bitwise AND zero.
static int findMaxK(int N)
{
    // Take k = N initially
    int K = N;
 
    // Start traversing from N-1 till 0
    for (int i = N - 1; i >= 0; i--) {
        K &= i;
 
        // Whenever we get AND as 0
        // we stop and return
        if (K == 0) {
            return i;
        }
    }
    return 0;
}
// Driver Code
    public static void main (String[] args) {
       int N = 5;
        System.out.println(findMaxK(N));
    }
}
// This code is contributed by Potta Lokesh

# Python 3 program for above approach
 
# Function to find maximum value of k
# which makes bitwise AND zero.
def findMaxK(N):
    # Take k = N initially
    K = N
 
    # Start traversing from N-1 till 0
    i = N-1
    while(i >= 0):
        K &= i
 
        # Whenever we get AND as 0
        # we stop and return
        if (K == 0):
            return i
        i -= 1
    return 0
 
# Driver Code
if __name__ == '__main__':
    N = 5
    print(findMaxK(N))
 
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
 
class GFG
{
 
  // Function to find maximum value of k
  // which makes bitwise AND zero.
  static int findMaxK(int N)
  {
 
    // Take k = N initially
    int K = N;
 
    // Start traversing from N-1 till 0
    for (int i = N - 1; i >= 0; i--) {
      K &= i;
 
      // Whenever we get AND as 0
      // we stop and return
      if (K == 0) {
        return i;
      }
    }
    return 0;
  }
 
  // Driver Code
  public static void Main (String[] args)
  {
    int N = 5;
    Console.Write(findMaxK(N));
  }
}
 
// This code is contributed by shivanisinghss2110

  <script>
        // JavaScript Program to implement
        // the above approach
 
  // Function to find maximum value of k
// which makes bitwise AND zero.
function findMaxK(N)
{
 
    // Take k = N initially
    let K = N;
 
    // Start traversing from N-1 till 0
    for (let i = N - 1; i >= 0; i--) {
        K &= i;
 
        // Whenever we get AND as 0
        // we stop and return
        if (K == 0) {
            return i;
        }
    }
    return 0;
}
         
 // Driver Code
      let N = 5;
      document.write(findMaxK(N));
 
// This code is contributed by sanjoy_62.
    </script>

3

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

Enfoque eficiente: mediante alguna observación, se puede ver que la respuesta siempre es igual a la potencia más alta de 2, que es menor o igual que (N-1). Finalmente, la respuesta siempre es igual a 2^K -1, donde K es un valor.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum value of k
// which makes bitwise AND zero.
int findMaxK(int N)
{
    // Finding the power less than N
    int p = log2(N);
    return pow(2, p);
}
 
// Driver Code
int main()
{
    int N = 5;
    cout << findMaxK(N) - 1 << endl;
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
    // Function to find maximum value of k
    // which makes bitwise AND zero.
    static int findMaxK(int N)
    {
        // Finding the power less than N
        int p = (int)(Math.log(N) / Math.log(2));
        return (int)Math.pow(2, p);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        System.out.println(findMaxK(N) - 1);
    }
}
 
// This code is contributed by maddler.

import math
 
# Function to find maximum value of k
# which makes bitwise AND zero.
def findMaxK(N):
   
    # Finding the power less than N
    p = math.log(N) // math.log(2);
    return int(pow(2, p));
 
# Driver Code
N = 5;
print(findMaxK(N) - 1);
 
# This code is contributed by _saurabh_jaiswal

/*package whatever //do not write package name here */
using System;
 
class GFG
{
 
    // Function to find maximum value of k
    // which makes bitwise AND zero.
    static int findMaxK(int N)
    {
       
        // Finding the power less than N
        int p = (int)(Math.Log(N) / Math.Log(2));
        return (int)Math.Pow(2, p);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 5;
        Console.Write(findMaxK(N) - 1);
    }
}
 
// This code is contributed by shivanisinghss2110

<script>
/*package whatever //do not write package name here */
 
// Function to find maximum value of k
// which makes bitwise AND zero.
function findMaxK(N)
{
// Finding the power less than N
var p = Math.log(N) / Math.log(2);
return parseInt(Math.pow(2, p));
}
 
    // Driver Code
var N = 5;
document.write(findMaxK(N) - 1);
 
// This code is contributed by 29AjayKumar
</script>

3

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