Given an integer N, the task is to find the minimum absolute difference between N and a power of 2.
Examples:
Input: N = 4
Output: 0
Power of 2 closest to 4 is 4. Therefore the minimum difference possible is 0.
Input: N = 9
Output: 1
Power of 2 closest to 9 is 8 and 9 – 8 = 1
Approach: Find the power of 2 closest to N on its left, left = 2floor(log2(N)) then the closest power of 2 on N’s right will be left * 2. Now the minimum absolute difference will be the minimum of N – left and right – N.
Below is the implementation of the above approach:
C++
// 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 2int 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 codeint main(){ int n = 15; cout << minAbsDiff(n); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{// Function to return the minimum difference // between N and a power of 2static 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 codepublic static void main(String args[]){ int n = 15; System.out.println(minAbsDiff(n));}}// This code is contributed by // Surendra_Gangwar |
Python3
# Python3 implementation of the # above approach # from math lib import floor# and log2 functionfrom 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#
// C# implementation of the above approachusing System;class GFG{// Function to return the minimum difference // between N and a power of 2static 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 codepublic static void Main(){ double n = 15; Console.Write(minAbsDiff(n));}}// This code is contributed by// Akanksha Rai |
PHP
<?php// PHP implementation of the above approach// Function to return the minimum difference // between N and a power of 2function 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 |
Javascript
<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> |
Output:
1
Time Complexity: O(1)
Auxiliary Space: O(1)
We can use left shift operator to optimize the implementation.
C++
// 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 2int 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 codeint main(){ int n = 15; cout << minAbsDiff(n); return 0;} |
Java
// Java implementation of the above approachclass GFG{ // Function to return the minimum difference // between N and a power of 2static 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 codepublic static void main (String[] args) { int n = 15; System.out.println(minAbsDiff(n));}}// This code is contributed by chandan_jnu |
Python3
# Python3 implementation of the# above approachimport math# Function to return the minimum # difference between N and a power of 2def 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 codeif __name__ == "__main__": n = 15 print(minAbsDiff(n))# This code is contributed # by 29AjayKumar |
C#
// C# implementation of the above approachusing System;public class GFG{// Function to return the minimum difference // between N and a power of 2static 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 codestatic public void Main (){ int n = 15; Console.WriteLine(minAbsDiff(n));}}// This code is contributed by jit_t. |
PHP
<?php // PHP implementation of the above approach// Function to return the minimum difference // between N and a power of 2function 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?> |
Javascript
<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> |
Output:
1
Time complexity : O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
