Encuentre el valor más pequeño de K tal que AND bit a bit de números en el rango [N, NK] sea 0

Posted on by Rudeus Greyrat

Dado un entero N , la tarea es encontrar el número más pequeño K tal que AND bit a bit de todos los números en el rango [N, NK] sea 0, es decir, N & (N – 1) & (N – 2) &… (N – K) = 0 .

Ejemplos:

Entrada: N = 17

Salida: 2

Explicación:

17 y 16 = 16

16 y 15 = 0

Como necesitamos encontrar el K más pequeño, nos detenemos aquí.

k = norte – 15 = 17 – 15 = 2

Entrada: N = 4

Salida: 1

Explicación:

4 y 3 = 0

Como necesitamos encontrar la k más pequeña, nos detenemos aquí.

 

Enfoque ingenuo: el enfoque más simple para resolver el problema es comenzar con el número dado y tomar AND bit a bit con un número menos que el número actual hasta que el AND bit a bit acumulativo no sea igual a 0 . Siga los pasos a continuación para resolver este problema:

  • Declare una variable cummAnd que almacene el AND conmutativo bit a bit e inicialícelo con n .
  • Declare una variable i e inicialícela con n – 1.
  • Ejecute un ciclo mientras cummAnd no es igual a 0:
    • cummand = cummand & i.
    • Disminuye i en 1.
  • Finalmente, imprima n – i.

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

C++

// C++ program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
 
#include <iostream>
using namespace std;
 
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
int findSmallestNumK(int n)
{
    int cummAnd = n;
 
    int i = n - 1;
    // Since, we need the largest no,
    // we start from n itself, till 0
    while (cummAnd != 0) {
 
        cummAnd = cummAnd & i;
        if (cummAnd == 0) {
            return i;
        }
 
        i--;
    }
 
    return -1;
}
 
// Driver Code
int main()
{
 
    int N = 17;
    int lastNum = findSmallestNumK(N);
    int K = lastNum == -1 ? lastNum : N - lastNum;
    cout << K << "\n";
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
    // Function is to find the largest no which gives the
    // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
    public static int findSmallestNumK(int n)
    {
        int cummAnd = n;
        int i = n - 1;
       
        // Since, we need the largest no,
        // we start from n itself, till 0
        while (cummAnd != 0) {
 
            cummAnd = cummAnd & i;
            if (cummAnd == 0) {
                return i;
            }
 
            i--;
        }
 
        return -1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 17;
        int lastNum = findSmallestNumK(N);
        int K = lastNum == -1 ? lastNum : N - lastNum;
        System.out.println(K);
       
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python3 program to find smallest value of K
# such that bitwise AND of numbers
# in range [N, N-K] is 0
 
# Function is to find the largest no which gives the
# sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
def findSmallestNumK(n):
     
    cummAnd = n
    i = n - 1
     
    # Since, we need the largest no,
    # we start from n itself, till 0
    while (cummAnd != 0):
        cummAnd = cummAnd & i
         
        if (cummAnd == 0):
            return i
 
        i -= 1
 
    return -1
 
# Driver Code
if __name__ == '__main__':
     
    N = 17
    lastNum = findSmallestNumK(N);
    K = lastNum if lastNum == -1 else N - lastNum
     
    print(K)
 
# This code is contributed by ipg2016107

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
public static int findSmallestNumK(int n)
{
    int cummAnd = n;
    int i = n - 1;
 
    // Since, we need the largest no,
    // we start from n itself, till 0
    while (cummAnd != 0)
    {
        cummAnd = cummAnd & i;
        if (cummAnd == 0)
        {
            return i;
        }
        i--;
    }
    return -1;
}
 
// Driver code
static void Main()
{
    int N = 17;
    int lastNum = findSmallestNumK(N);
    int K = lastNum == -1 ? lastNum : N - lastNum;
     
    Console.WriteLine(K);
}
}
 
// This code is contributed by abhinavjain194

Javascript

<script>
       // JavaScript program for the above approach
 
       // Function is to find the largest no which gives the
       // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
       function findSmallestNumK(n)
       {
           let cummAnd = n;
 
           let i = n - 1;
            
           // Since, we need the largest no,
           // we start from n itself, till 0
           while (cummAnd != 0) {
 
               cummAnd = cummAnd & i;
               if (cummAnd == 0) {
                   return i;
               }
 
               i--;
           }
 
           return -1;
       }
 
       // Driver Code
       let N = 17;
       let lastNum = findSmallestNumK(N);
       let K = lastNum == -1 ? lastNum : N - lastNum;
       document.write(K + "<br>");
 
 // This code is contributed by Potta Lokesh
   </script>
Producción

2

Complejidad de tiempo : O(N)

Espacio Auxiliar : O(1)

Enfoque eficiente: este problema se puede resolver utilizando las propiedades del operador AND bit a bit, es decir, si ambos bits están configurados, solo el resultado será distinto de cero. Entonces, tenemos que encontrar la mayor potencia de 2 , que es menor o igual a N (digamos X ). Siga los pasos a continuación para resolver este problema:

  • La función log2(n) da la potencia de 2 , que es igual a n .
  • Ya que, su tipo de retorno es doble. Así que usamos la función Floor para obtener la mayor potencia de 2 , que es menor o igual que n y la almacenamos en X.
  • X = (1 << X) – 1.
  • Finalmente, imprima N – X.

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

C++

// C++ program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
 
#include <bits/stdc++.h>
using namespace std;
 
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
int findSmallestNumK(int n)
{
 
    // find largest power of 2
    // less than or equal to n
    int larPowOfTwo = floor(log2(n));
 
    larPowOfTwo = 1 << larPowOfTwo;
 
    return larPowOfTwo - 1;
}
 
// Driver Code
int main()
{
 
    int N = 17;
    int lastNum = findSmallestNumK(N);
    int K = lastNum == -1 ? lastNum : N - lastNum;
    cout << K << "\n";
    return 0;
}

C

// C program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
 
#include <math.h> //for log2
#include <stdio.h>
 
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
int findSmallestNumK(int n)
{
 
  // find largest power of 2
  // less than or equal to n
  int larPowOfTwo = floor(log2(n));
 
  larPowOfTwo = 1 << larPowOfTwo;
 
  return larPowOfTwo - 1;
}
 
// Driver Code
int main()
{
 
  int N = 17;
  int lastNum = findSmallestNumK(N);
  int K = lastNum == -1 ? lastNum : N - lastNum;
  printf("%d\n", K);
  return 0;
}
 
// This code is contributed by phalashi.

Java

// Java program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
import java.io.*;
 
class GFG {
 
    // Function is to find the largest no which gives the
    // sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
    static int findSmallestNumK(int n)
    {
 
        // find largest power of 2
        // less than or equal to n
        int larPowOfTwo
            = (int)Math.floor(Math.log(n) / Math.log(2));
 
        larPowOfTwo = 1 << larPowOfTwo;
 
        return larPowOfTwo - 1;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int N = 17;
        int lastNum = findSmallestNumK(N);
        int K = lastNum == -1 ? lastNum : N - lastNum;
        System.out.println(K);
    }
}
 
// This code is contributed by rishavmahato348.

Python3

# Python program to find smallest value of K
# such that bitwise AND of numbers
# in range [N, N-K] is 0
# Function is to find the largest no which gives the
# sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
import math
 
def findSmallestNumK( n):
 
 
    # find largest power of 2
    # less than or equal to n
    larPowOfTwo = math.floor(math.log2(n))
 
    larPowOfTwo = 1 << larPowOfTwo
 
    return larPowOfTwo - 1
 
 
# Driver Code
N = 17
lastNum = findSmallestNumK(N)
K = lastNum if (lastNum == -1 ) else N - lastNum
print(K)
 
# this code is contributed by shivanisinghss2110

C#

// C# program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
using System;
 
class GFG{
 
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
static int findSmallestNumK(int n)
{
     
    // Find largest power of 2
    // less than or equal to n
    int larPowOfTwo = (int)Math.Floor(Math.Log(n) /
                                      Math.Log(2));
 
    larPowOfTwo = 1 << larPowOfTwo;
 
    return larPowOfTwo - 1;
}
 
// Driver Code
public static void Main()
{
    int N = 17;
    int lastNum = findSmallestNumK(N);
    int K = lastNum == -1 ? lastNum : N - lastNum;
     
    Console.Write(K);
}
}
 
// This code is contributed by subhammahato348

Javascript

<script>
 
// JavaScript program to find smallest value of K
// such that bitwise AND of numbers
// in range [N, N-K] is 0
// Function is to find the largest no which gives the
// sequence n & (n - 1) & (n - 2)&.....&(n - k) = 0.
function findSmallestNumK(n)
    {
 
        // find largest power of 2
        // less than or equal to n
        var larPowOfTwo
            = Math.floor(Math.log(n) / Math.log(2));
 
        larPowOfTwo = 1 << larPowOfTwo;
 
        return larPowOfTwo - 1;
    }
 
// Driver Code
    var N = 17;
    var lastNum = findSmallestNumK(N);
    var K = lastNum == -1 ? lastNum : N - lastNum;
    document.write(K);
  
// This code is contributed by shivanisinghss2110
 
</script>
Producción

2

Complejidad de tiempo: O (log N)

Complejidad espacial: O(1)

Publicación traducida automáticamente

Artículo escrito por nishyadav123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *