Minimum absolute difference between N and any power of 2
Given a positive integer N, the task is to find the minimum absolute difference between N and any power of 2.
Examples:
Input: N = 3
Output: 1
Smaller power of 2 nearest to 3 is 2, abs(3 – 2) = 1
Higher power of 2 nearest to 3 is 4, abs(4 – 3) = 1Input: N = 6
Output: 2
Approach:
- Find the highest power of 2 less than or equal to N and store it in a variable low.
- Find the smallest power of 2 greater than or equal to N and store it in a variable high.
- Now, the answer will be max(N – low, high – N).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the highest power // of 2 less than or equal to n int prevPowerof2( int n) { int p = ( int )log2(n); return ( int ) pow (2, p); } // Function to return the smallest power // of 2 greater than or equal to n int nextPowerOf2( int n) { int p = 1; if (n && !(n & (n - 1))) return n; while (p < n) p <<= 1; return p; } // Function that returns the minimum // absolute difference between n // and any power of 2 int minDiff( int n) { int low = prevPowerof2(n); int high = nextPowerOf2(n); return min(n - low, high - n); } // Driver code int main() { int n = 6; cout << minDiff(n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to return the highest power // of 2 less than or equal to n static int prevPowerof2( int n) { int p = ( int )(Math.log(n) / Math.log( 2 )); return ( int )Math.pow( 2 , p); } // Function to return the smallest power // of 2 greater than or equal to n static int nextPowerOf2( int n) { int p = 1 ; if ((n == 0 ) && !((n & (n - 1 )) == 0 )) return n; while (p < n) p <<= 1 ; return p; } // Function that returns the minimum // absolute difference between n // and any power of 2 static int minDiff( int n) { int low = prevPowerof2(n); int high = nextPowerOf2(n); return Math.min(n - low, high - n); } // Driver code public static void main (String[] args) { int n = 6 ; System.out.println(minDiff(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach from math import log # Function to return the highest power # of 2 less than or equal to n def prevPowerof2(n): p = int (log(n)) return pow ( 2 , p) # Function to return the smallest power # of 2 greater than or equal to n def nextPowerOf2(n): p = 1 if (n and (n & (n - 1 )) = = 0 ): return n while (p < n): p << = 1 return p # Function that returns the minimum # absolute difference between n # and any power of 2 def minDiff(n): low = prevPowerof2(n) high = nextPowerOf2(n) return min (n - low, high - n) # Driver code n = 6 print (minDiff(n)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the highest power // of 2 less than or equal to n static int prevPowerof2( int n) { int p = ( int )(Math.Log(n) / Math.Log(2)); return ( int )Math.Pow(2, p); } // Function to return the smallest power // of 2 greater than or equal to n static int nextPowerOf2( int n) { int p = 1; if ((n == 0) && !((n & (n - 1)) == 0)) return n; while (p < n) p <<= 1; return p; } // Function that returns the minimum // absolute difference between n // and any power of 2 static int minDiff( int n) { int low = prevPowerof2(n); int high = nextPowerOf2(n); return Math.Min(n - low, high - n); } // Driver code public static void Main (String []args) { int n = 6; Console.WriteLine(minDiff(n)); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // Javascript implementation of the approach // Function to return the highest power // of 2 less than or equal to n function prevPowerof2(n) { var p = parseInt(Math.log(n)/Math.log(2)); return parseInt(Math.pow(2, p)); } // Function to return the smallest power // of 2 greater than or equal to n function nextPowerOf2(n) { var p = 1; if (n && !(n & (n - 1))) return n; while (p < n) p <<= 1; return p; } // Function that returns the minimum // absolute difference between n // and any power of 2 function minDiff(n) { var low = prevPowerof2(n); var high = nextPowerOf2(n); return Math.min(n - low, high - n); } // Driver code var n = 6; document.write(minDiff(n)); // This code is contributed by noob2000. </script> |
Output
2
Time Complexity: O(log N)
Auxiliary Space: O(1)