Given a circular array arr[] consisting of N integers, the task is to replace all the array elements with the nearest possible power of its previous adjacent element
Examples:
Input: arr[] = {2, 4, 6, 3, 11}
Output: 1 4 4 6 9
Explanation:
Power of 11 which is nearest to 2 —> 110 = 1
Power of 2 which is nearest to 4 —> 22 = 4
Power of 4 which is nearest to 6 —> 41 = 4
Power of 6 which is nearest to 3 —> 61 = 6
Power of 3 which is nearest to 11—> 32 = 9Input: arr[] = {3, 2, 4, 3}
Output: 3 3 4 4
Explanation:
Power of 3 which is nearest to 3 —> 31 = 3
Power of 3 which is nearest to 2 —> 31 = 3
Power of 2 which is nearest to 4 —> 22 = 4
Power of 4 which is nearest to 3 —> 41 = 4
Approach: The idea to solve this problem is to traverse the array and for each array element arr[i], find the power of the previous element, say X, which is nearest to arr[i], i.e. XK which is closest to arr[i]. Follow the steps:
- Calculate the value of K, which is equal to the floor value of logx(Y).
- Therefore, K and (K + 1) will be the two integers for which the power could be nearest.
- Calculate XK and X(K + 1) and check which is nearer to Y. Then, print that value.
Below is the implementation of the above approach:
C++
// CPP program for the above approach #include <iostream> #include <cmath> using namespace std; // Function to calculate log x for given base int LOG( int a, int b) { return log (a) / log (b); } // Function to replace all array // elements with the nearest power // of previous adjacent nelement void repbyNP( int *arr, int n) { // For the first element, set the last // array element to its previous element int x = arr[n - 1]; // Traverse the array for ( int i = 0; i < n; i++) { // Find K for which x ^ k is // nearest to arr[i] int k = LOG(arr[i], x); int temp = arr[i]; // Find the power to x nearest to arr[i] if ( abs ( pow (x,k) - arr[i]) < abs ( pow (x,k+1) - arr[i])) arr[i] = pow (x, k); else arr[i] = pow (x, k + 1); // Update x x = temp; } } int main() { // Driver Code int arr[5] = {2, 4, 6, 3, 11}; int n = sizeof (arr)/ sizeof (arr[0]); // Function Call repbyNP(arr,n); // Display the array for ( int i = 0; i < n; i++) cout<<arr[i]<< " " ; return 0; } // This code is contributed by rohitsingh07052. |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to calculate log x for given base static int LOG( int a, int b) { return ( int )(Math.log(a) / Math.log(b)); } // Function to replace all array // elements with the nearest power // of previous adjacent nelement static void repbyNP( int [] arr, int n) { // For the first element, set the last // array element to its previous element int x = arr[n - 1 ]; // Traverse the array for ( int i = 0 ; i < n; i++) { // Find K for which x ^ k is // nearest to arr[i] int k = LOG(arr[i], x); int temp = arr[i]; // Find the power to x nearest to arr[i] if (Math.abs(Math.pow(x,k) - arr[i]) < Math.abs(Math.pow(x,k+ 1 ) - arr[i])) arr[i] = ( int )Math.pow(x, k); else arr[i] = ( int )Math.pow(x, k + 1 ); // Update x x = temp; } } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 4 , 6 , 3 , 11 }; int n = arr.length; // Function Call repbyNP(arr,n); // Display the array for ( int i = 0 ; i < n; i++) System.out.print(arr[i] + " " ); } } // This code is contributed by sanjoy_62. |
Python3
# Python3 program for the above approach import math # Function to calculate log x for given base def LOG(x, base): return int (math.log(x) / math.log(base)) # Function to replace all array # elements with the nearest power # of previous adjacent nelement def repbyNP(arr): # For the first element, set the last # array element to its previous element x = arr[ - 1 ] # Traverse the array for i in range ( len (arr)): # Find K for which x ^ k is # nearest to arr[i] k = LOG(arr[i], x) temp = arr[i] # Find the power to x nearest to arr[i] if abs (x * * k - arr[i]) < abs (x * * (k + 1 ) - arr[i]): arr[i] = x * * k else : arr[i] = x * * (k + 1 ) # Update x x = temp # Return the array return arr # Driver Code arr = [ 2 , 4 , 6 , 3 , 11 ] # Function Call print (repbyNP(arr)) |
C#
// C# program for the above approach using System; class GFG{ // Function to calculate log x for given base static int LOG( int a, int b) { return ( int )(Math.Log(a) / Math.Log(b)); } // Function to replace all array // elements with the nearest power // of previous adjacent nelement static void repbyNP( int [] arr, int n) { // For the first element, set the last // array element to its previous element int x = arr[n - 1]; // Traverse the array for ( int i = 0; i < n; i++) { // Find K for which x ^ k is // nearest to arr[i] int k = LOG(arr[i], x); int temp = arr[i]; // Find the power to x nearest to arr[i] if (Math.Abs(Math.Pow(x, k) - arr[i]) < Math.Abs(Math.Pow(x, k + 1) - arr[i])) arr[i] = ( int )Math.Pow(x, k); else arr[i] = ( int )Math.Pow(x, k + 1); // Update x x = temp; } } // Driver Code public static void Main( string [] args) { int [] arr = {2, 4, 6, 3, 11}; int n = arr.Length; // Function Call repbyNP(arr,n); // Display the array for ( int i = 0; i < n; i++) Console.Write(arr[i] + " " ); } } // This code is contributed by code_hunt. |
Javascript
<script> // Javascript program for the above approach // Function to calculate log x for given base function LOG(a, b) { return parseInt(Math.log(a) / Math.log(b)); } // Function to replace all array // elements with the nearest power // of previous adjacent nelement function repbyNP(arr, n) { // For the first element, set the last // array element to its previous element let x = arr[n - 1]; // Traverse the array for (let i = 0; i < n; i++) { // Find K for which x ^ k is // nearest to arr[i] let k = LOG(arr[i], x); let temp = arr[i]; // Find the power to x nearest to arr[i] if (Math.abs(Math.pow(x, k) - arr[i]) < Math.abs(Math.pow(x, k + 1) - arr[i])) arr[i] = Math.pow(x, k); else arr[i] = Math.pow(x, k + 1); // Update x x = temp; } } // Driver Code let arr = [2, 4, 6, 3, 11]; let n = arr.length; // Function Call repbyNP(arr, n); // Display the array for (let i = 0; i < n; i++) document.write(arr[i] + " " ); // This code is contributed by rishavmahato348. </script> |
[1, 4, 4, 1, 9]
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!