Finden Sie die nächste Potenz von 2 für jedes Array-Element
Bei einem Array arr[] der Größe N besteht die Aufgabe darin, die nächste Potenz von 2 für jedes Array-Element auszugeben.
Hinweis: Wenn es zufällig zwei nächste Potenzen von 2 gibt, betrachten Sie die größere.
Beispiele:
Eingabe: arr[] = {5, 2, 7, 12}
Ausgabe: 4 2 8 16
Erläuterung:
Die nächste Potenz von arr[0] ( = 5) ist 4.
Die nächste Potenz von arr[1] ( = 2) ist 2.
Die nächste Potenz von arr[2] ( = 7) ist 8.
Die nächste Potenz von arr[3] ( = 12) ist 8 und 16. Geben Sie 16 aus, da es die größte ist.Eingabe: arr[] = {31, 13, 64}
Ausgabe: 32 16 64
Vorgehensweise: Führen Sie die folgenden Schritte aus, um das Problem zu lösen:
- Durchlaufen Sie das Array von links nach rechts.
- Finden Sie für jedes Array-Element die nächsten Potenzen von 2 größer und kleiner als es, dh berechnen Sie pow(2, log 2 (arr[i])) und pow(2, log 2 (arr[i]) + 1) .
- Berechnen Sie die Differenz dieser beiden Werte aus dem aktuellen Array-Element und drucken Sie den nächsten, wie in der Problemstellung angegeben.
Unten ist die Implementierung des obigen Ansatzes:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find nearest power of two // for every element in the given array void nearestPowerOfTwo(int arr[], int N) { // Traverse the array for (int i = 0; i < N; i++) { // Calculate log of the // current array element int lg = log2(arr[i]); int a = pow(2, lg); int b = pow(2, lg + 1); // Find the nearest if ((arr[i] - a) < (b - arr[i])) cout << a << " "; else cout << b << " "; } } // Driver Code int main() { int arr[] = { 5, 2, 7, 12 }; int N = sizeof(arr) / sizeof(arr[0]); nearestPowerOfTwo(arr, N); return 0; }
Java
// Java program to implement the above approach import java.io.*; class GFG { // Function to find the nearest power of two // for every element of the given array static void nearestPowerOfTwo(int[] arr, int N) { // Traverse the array for (int i = 0; i < N; i++) { // Calculate log of the // current array element int lg = (int)(Math.log(arr[i]) / Math.log(2)); int a = (int)(Math.pow(2, lg)); int b = (int)(Math.pow(2, lg + 1)); // Find the nearest if ((arr[i] - a) < (b - arr[i])) System.out.print(a + " "); else System.out.print(b + " "); } } // Driver Code public static void main(String[] args) { int[] arr = { 5, 2, 7, 12 }; int N = arr.length; nearestPowerOfTwo(arr, N); } }
Python3
# Python program to implement the above approach import math # Function to find the nearest power # of two for every array element def nearestPowerOfTwo(arr, N): # Traverse the array for i in range(N): # Calculate log of current array element lg = (int)(math.log2(arr[i])) a = (int)(math.pow(2, lg)) b = (int)(math.pow(2, lg + 1)) # Find the nearest if ((arr[i] - a) < (b - arr[i])): print(a, end = " ") else: print(b, end = " ") # Driver Code arr = [5, 2, 7, 12] N = len(arr) nearestPowerOfTwo(arr, N)
C#
// C# program to implement the above approach using System; class GFG { // Function to find nearest power of two // for every array element static void nearestPowerOfTwo(int[] arr, int N) { // Traverse the array for (int i = 0; i < N; i++) { // Calculate log of the // current array element int lg = (int)(Math.Log(arr[i]) / Math.Log(2)); int a = (int)(Math.Pow(2, lg)); int b = (int)(Math.Pow(2, lg + 1)); // Find the nearest if ((arr[i] - a) < (b - arr[i])) Console.Write(a + " "); else Console.Write(b + " "); } } // Driver Code public static void Main(String[] args) { int[] arr = { 5, 2, 7, 12 }; int N = arr.Length; nearestPowerOfTwo(arr, N); } }
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the nearest power of two // for every element of the given array function nearestPowerOfTwo(arr , N) { // Traverse the array for (i = 0; i < N; i++) { // Calculate log of the // current array element var lg = parseInt( (Math.log(arr[i]) / Math.log(2))); var a = parseInt( (Math.pow(2, lg))); var b = parseInt( (Math.pow(2, lg + 1))); // Find the nearest if ((arr[i] - a) < (b - arr[i])) document.write(a + " "); else document.write(b + " "); } } // Driver Code var arr = [ 5, 2, 7, 12 ]; var N = arr.length; nearestPowerOfTwo(arr, N); // This code is contributed by todaysgaurav </script>
4 2 8 16
Zeitkomplexität: O(N)
Hilfsraum: O(1)
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .