Given an array arr[] consisting of N positive integers and two positive integers A and B, the task is to replace each array element with the absolute difference of the nearest powers of A and B. If there exists two nearest powers, then choose the maximum of the two.
Examples:
Input: arr[] = {5, 12, 25}, A = 2, B = 3
Output: 1 7 5
Explanation:
- For element arr[0]( = 5): The nearest power of 2 is 4 and the nearest power of 3 is 3. Therefore, the absolute difference of 4 and 3 is 1.
- For arr[1]( = 12): The nearest power of 2 is 16 and the nearest power of 3 is 9. Therefore, the absolute difference of 16 and 9 is 7.
- For arr[2]( = 5): The nearest power of 2 is 32 and the nearest power of 3 is 27. Therefore, the absolute difference of 27 and 32 is 5.
Therefore, the modified array is {1, 7, 5}.
Input: arr[] = {32, 3, 7}, a = 2, b = 3
Output: 0 1 1
Approach: The given problem can be solved by finding both the nearest power of A and B for every array element and update it to the absolute difference of the two values obtained.
Follow the steps to solve the problem
- Traverse the given array arr[] and perform the following steps:
- Find the two values that are the perfect powers of a less than and greater than arr[i] and find the closest of the two values.
- Find the two values that are the perfect powers of b less than and greater than arr[i] and find the closest of the two values.
- Find the absolute difference between the two closest values obtained and update arr[i] with it.
- After completing the above steps, print the modified array arr[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the arrayvoid printArray(int arr[], int N){ // Traverse the array for (int i = 0; i < N; i++) { cout << arr[i] << " "; }}// Function to modify array elements// by absolute difference of the// nearest perfect power of a and bvoid nearestPowerDiff(int arr[], int N, int a, int b){ // Traverse the array arr[] for (int i = 0; i < N; i++) { // Find the log a of arr[i] int log_a = log(arr[i]) / log(a); // Find the power of a less // than and greater than a int A = pow(a, log_a); int B = pow(a, log_a + 1); if ((arr[i] - A) < (B - arr[i])) log_a = A; else log_a = B; // Find the log b of arr[i] int log_b = log(arr[i]) / log(b); // Find the power of b less than // and greater than b A = pow(b, log_b); B = pow(b, log_b + 1); if ((arr[i] - A) < (B - arr[i])) log_b = A; else log_b = B; // Update arr[i] with absolute // difference of log_a & log _b arr[i] = abs(log_a - log_b); } // Print the modified array printArray(arr, N);}// Driver Codeint main(){ int arr[] = { 5, 12, 25 }; int A = 2, B = 3; int N = sizeof(arr) / sizeof(arr[0]); nearestPowerDiff(arr, N, A, B); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to print the arraystatic void printArray(int[] arr, int N){ // Traverse the array for(int i = 0; i < N; i++) { System.out.print(arr[i] + " "); }}// Function to modify array elements// by absolute difference of the// nearest perfect power of a and bstatic void nearestPowerDiff(int[] arr, int N, int a, int b){ // Traverse the array arr[] for(int i = 0; i < N; i++) { // Find the log a of arr[i] int log_a = (int)(Math.log(arr[i]) / Math.log(a)); // Find the power of a less // than and greater than a int A = (int)(Math.pow(a, log_a)); int B = (int)(Math.pow(a, log_a + 1)); if ((arr[i] - A) < (B - arr[i])) log_a = A; else log_a = B; // Find the log b of arr[i] int log_b = (int)(Math.log(arr[i]) / Math.log(b)); // Find the power of b less than // and greater than b A = (int)(Math.pow(b, log_b)); B = (int)(Math.pow(b, log_b + 1)); if ((arr[i] - A) < (B - arr[i])) log_b = A; else log_b = B; // Update arr[i] with absolute // difference of log_a & log _b arr[i] = Math.abs(log_a - log_b); } // Print the modified array printArray(arr, N);}// Driver Codepublic static void main(String[] args){ int[] arr = { 5, 12, 25 }; int A = 2, B = 3; int N = arr.length; nearestPowerDiff(arr, N, A, B);}}// This code is contributed by subham348 |
Python3
# Python3 program for the above approachimport math# Function to print the arraydef printArray(arr, N): # Traverse the array for i in range(N): print(arr[i], end = " ") # Function to modify array elements# by absolute difference of the# nearest perfect power of a and bdef nearestPowerDiff(arr, N, a, b): # Traverse the array arr[] for i in range(N): # Find the log a of arr[i] log_a = int(math.log(arr[i]) / math.log(a)) # Find the power of a less # than and greater than a A = int(pow(a, log_a)) B = int(pow(a, log_a + 1)) if ((arr[i] - A) < (B - arr[i])): log_a = A else: log_a = B # Find the log b of arr[i] log_b = int(math.log(arr[i]) / math.log(b)) # Find the power of b less than # and greater than b A = int(pow(b, log_b)) B = int(pow(b, log_b + 1)) if ((arr[i] - A) < (B - arr[i])): log_b = A else: log_b = B # Update arr[i] with absolute # difference of log_a & log _b arr[i] = abs(log_a - log_b) # Print the modified array printArray(arr, N)# Driver Codearr = [ 5, 12, 25 ]A = 2B = 3N = len(arr)nearestPowerDiff(arr, N, A, B)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing System;public class GFG{// Function to print the arraystatic void printArray(int[] arr, int N){ // Traverse the array for(int i = 0; i < N; i++) { Console.Write(arr[i] + " "); }}// Function to modify array elements// by absolute difference of the// nearest perfect power of a and bstatic void nearestPowerDiff(int[] arr, int N, int a, int b){ // Traverse the array arr[] for(int i = 0; i < N; i++) { // Find the log a of arr[i] int log_a = (int)(Math.Log(arr[i]) / Math.Log(a)); // Find the power of a less // than and greater than a int A = (int)(Math.Pow(a, log_a)); int B = (int)(Math.Pow(a, log_a + 1)); if ((arr[i] - A) < (B - arr[i])) log_a = A; else log_a = B; // Find the log b of arr[i] int log_b = (int)(Math.Log(arr[i]) / Math.Log(b)); // Find the power of b less than // and greater than b A = (int)(Math.Pow(b, log_b)); B = (int)(Math.Pow(b, log_b + 1)); if ((arr[i] - A) < (B - arr[i])) log_b = A; else log_b = B; // Update arr[i] with absolute // difference of log_a & log _b arr[i] = Math.Abs(log_a - log_b); } // Print the modified array printArray(arr, N);}// Driver Codepublic static void Main(string[] args){ int[] arr = { 5, 12, 25 }; int A = 2, B = 3; int N = arr.Length; nearestPowerDiff(arr, N, A, B);}}// This code is contributed by AnkThon |
Javascript
<script>// JavaScript implementation of the above approach// Function to print the arrayfunction printArray(arr, N){ // Traverse the array for(let i = 0; i < N; i++) { document.write(arr[i] + " "); }} // Function to modify array elements// by absolute difference of the// nearest perfect power of a and bfunction nearestPowerDiff(arr, N, a, b){ // Traverse the array arr[] for(let i = 0; i < N; i++) { // Find the log a of arr[i] let log_a = Math.floor(Math.log(arr[i]) / Math.log(a)); // Find the power of a less // than and greater than a let A = Math.floor(Math.pow(a, log_a)); let B = Math.floor(Math.pow(a, log_a + 1)); if ((arr[i] - A) < (B - arr[i])) log_a = A; else log_a = B; // Find the log b of arr[i] let log_b = Math.floor(Math.log(arr[i]) / Math.log(b)); // Find the power of b less than // and greater than b A = Math.floor(Math.pow(b, log_b)); B = Math.floor(Math.pow(b, log_b + 1)); if ((arr[i] - A) < (B - arr[i])) log_b = A; else log_b = B; // Update arr[i] with absolute // difference of log_a & log _b arr[i] = Math.abs(log_a - log_b); } // Print the modified array printArray(arr, N);} // Driver code let arr = [ 5, 12, 25 ]; let A = 2, B = 3; let N = arr.length; nearestPowerDiff(arr, N, A, B); // This code is contributed by susmitakundugoaldanga.</script> |
Output:
1 7 5
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!
