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 baseint LOG(int a, int b) { return log(a) / log(b); } // Function to replace all array// elements with the nearest power// of previous adjacent nelementvoid 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 approachimport java.util.*; class GFG{ // Function to calculate log x for given basestatic 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 nelementstatic 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 Codepublic 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 approachimport math# Function to calculate log x for given basedef LOG(x, base): return int(math.log(x)/math.log(base))# Function to replace all array# elements with the nearest power# of previous adjacent nelementdef 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 Codearr = [2, 4, 6, 3, 11]# Function Callprint(repbyNP(arr)) |
C#
// C# program for the above approachusing System;class GFG{// Function to calculate log x for given basestatic 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 nelementstatic 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 Codepublic 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 basefunction LOG(a, b) { return parseInt(Math.log(a) / Math.log(b)); } // Function to replace all array// elements with the nearest power// of previous adjacent nelementfunction 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> |
Output:
[1, 4, 4, 1, 9]
Time Complexity: O(N)
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!
