Diferencia mínima absoluta entre N y una potencia de 2

Dado un número entero N , la tarea es encontrar la mínima diferencia absoluta entre N y una potencia de 2 .
Ejemplos: 
 

Entrada: N = 4 
Salida: 0 
La potencia de 2 más cercana a 4 es 4. Por lo tanto, la diferencia mínima posible es 0.
Entrada: N = 9 
Salida: 1 
La potencia de 2 más cercana a 9 es 8 y 9 – 8 = 1 
 

Enfoque: encuentre la potencia de 2 más cercana a N a su izquierda, izquierda = 2 ^{piso (log2 (N))} , luego la potencia de 2 más cercana a la derecha de N será izquierda * 2 . Ahora la mínima diferencia absoluta será el mínimo de N – izquierda y derecha – N .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum difference
// between N and a power of 2
int minAbsDiff(int n)
{
    // Power of 2 closest to n on its left
    int left = pow(2, floor(log2(n)));
 
    // Power of 2 closest to n on its right
    int right = left * 2;
 
    // Return the minimum abs difference
    return min((n - left), (right - n));
}
 
// Driver code
int main()
{
    int n = 15;
    cout << minAbsDiff(n);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
// Function to return the minimum difference
// between N and a power of 2
static int minAbsDiff(int n)
{
    // Power of 2 closest to n on its left
    int left = (int)Math.pow(2, (int)(Math.log(n) /
                                Math.log(2)));
 
    // Power of 2 closest to n on its right
    int right = left * 2;
 
    // Return the minimum abs difference
    return Math.min((n - left), (right - n));
}
 
// Driver code
public static void main(String args[])
{
    int n = 15;
    System.out.println(minAbsDiff(n));
}
}
 
// This code is contributed by
// Surendra_Gangwar

# Python3 implementation of the
# above approach
 
# from math lib import floor
# and log2 function
from math import floor, log2
 
# Function to return the minimum
# difference between N and a power of 2
def minAbsDiff(n) :
     
    # Power of 2 closest to n on its left
    left = pow(2, floor(log2(n)))
 
    # Power of 2 closest to n on its right
    right = left * 2
 
    # Return the minimum abs difference
    return min((n - left), (right - n))
 
# Driver code
if __name__ == "__main__" :
 
    n = 15
    print(minAbsDiff(n))
 
# This code is contributed by Ryuga

// C# implementation of the above approach
using System;
 
class GFG
{
// Function to return the minimum difference
// between N and a power of 2
static double minAbsDiff(double n)
{
    // Power of 2 closest to n on its left
    double left = Math.Pow(2,
                Math.Floor(Math.Log(n, 2)));
 
    // Power of 2 closest to n on its right
    double right = left * 2;
 
    // Return the minimum abs difference
    return Math.Min((n - left), (right - n));
}
 
// Driver code
public static void Main()
{
    double n = 15;
    Console.Write(minAbsDiff(n));
}
}
 
// This code is contributed by
// Akanksha Rai

<?php
// PHP implementation of the above approach
 
// Function to return the minimum difference
// between N and a power of 2
function minAbsDiff($n)
{
    // Power of 2 closest to n on its left
    $left = pow(2, floor(log($n, 2)));
 
    // Power of 2 closest to n on its right
    $right = $left * 2;
 
    // Return the minimum abs difference
    return min(($n - $left), ($right - $n));
}
 
// Driver code
$n = 15;
echo minAbsDiff($n);
 
// This code is contributed
// by Akanksha Rai

<script>
 
    // Javascript implementation of the above approach
     
    // Function to return the minimum difference
    // between N and a power of 2
    function minAbsDiff(n)
    {
        // Power of 2 closest to n on its left
        let left = Math.pow(2, Math.floor(Math.log2(n, 2)));
 
        // Power of 2 closest to n on its right
        let right = left * 2;
 
        // Return the minimum abs difference
        return Math.min((n - left), (right - n));
    }
     
    let n = 15;
    document.write(minAbsDiff(n));
     
</script>

1

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Podemos usar el operador de desplazamiento a la izquierda para optimizar la implementación. 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum difference
// between N and a power of 2
int minAbsDiff(int n)
{
    // Power of 2 closest to n on its left
    int left = 1 << ((int)floor(log2(n)));
 
    // Power of 2 closest to n on its right
    int right = left * 2;
 
    // Return the minimum abs difference
    return min((n - left), (right - n));
}
 
// Driver code
int main()
{
    int n = 15;
    cout << minAbsDiff(n);
    return 0;
}

// Java implementation of the above approach
class GFG
{
     
// Function to return the minimum difference
// between N and a power of 2
static int minAbsDiff(int n)
{
    // Power of 2 closest to n on its left
    int left = 1 << ((int)Math.floor(Math.log(n) / Math.log(2)));
 
    // Power of 2 closest to n on its right
    int right = left * 2;
 
    // Return the minimum abs difference
    return Math.min((n - left), (right - n));
}
 
// Driver code
public static void main (String[] args)
{
    int n = 15;
    System.out.println(minAbsDiff(n));
}
}
 
// This code is contributed by chandan_jnu

# Python3 implementation of the
# above approach
import math
 
# Function to return the minimum
# difference between N and a power of 2
def minAbsDiff(n):
     
    # Power of 2 closest to n on its left
    left = 1 << (int)(math.floor(math.log2(n)))
 
    # Power of 2 closest to n on its right
    right = left * 2
 
    # Return the minimum abs difference
    return min((n - left), (right - n))
 
# Driver code
if __name__ == "__main__":
    n = 15
    print(minAbsDiff(n))
 
# This code is contributed
# by 29AjayKumar

// C# implementation of the above approach
using System;
 
public class GFG
{
 
// Function to return the minimum difference
// between N and a power of 2
static int minAbsDiff(int n)
{
    // Power of 2 closest to n on its left
    int left = 1 << ((int)Math.Floor(Math.Log(n) / Math.Log(2)));
 
    // Power of 2 closest to n on its right
    int right = left * 2;
 
    // Return the minimum abs difference
    return Math.Min((n - left), (right - n));
}
 
// Driver code
static public void Main ()
{
    int n = 15;
    Console.WriteLine(minAbsDiff(n));
}
}
 
// This code is contributed by jit_t.

<?php
// PHP implementation of the above approach
 
// Function to return the minimum difference
// between N and a power of 2
function minAbsDiff($n)
{
    // Power of 2 closest to n on its left
    $left = 1 << ((floor(log($n) / log(2))));
 
    // Power of 2 closest to n on its right
    $right = $left * 2;
 
    // Return the minimum abs difference
    return min(($n - $left), ($right - $n));
}
 
// Driver code
$n = 15;
echo minAbsDiff($n);
 
// This code is contributed by ita_c
?>

<script>
    // Javascript implementation of the above approach
     
    // Function to return the minimum difference
    // between N and a power of 2
    function minAbsDiff(n)
    {
        // Power of 2 closest to n on its left
        let left = 1 << (Math.floor(Math.log(n) / Math.log(2)));
 
        // Power of 2 closest to n on its right
        let right = left * 2;
 
        // Return the minimum abs difference
        return Math.min((n - left), (right - n));
    }
     
    let n = 15;
    document.write(minAbsDiff(n));
 
</script>

1

Complejidad del tiempo : O(1)

Espacio Auxiliar: O(1)