Replace all array elements with the nearest power of its previous element

Replace all array elements with the nearest power of its previous element

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 —> 11⁰ = 1
Power of 2 which is nearest to 4 —> 2² = 4
Power of 4 which is nearest to 6 —> 4¹ = 4
Power of 6 which is nearest to 3 —> 6¹ = 6
Power of 3 which is nearest to 11—> 3² = 9

Input: arr[] = {3, 2, 4, 3}
Output: 3 3 4 4
Explanation:
Power of 3 which is nearest to 3 —> 3¹ = 3
Power of 3 which is nearest to 2 —> 3¹ = 3
Power of 2 which is nearest to 4 —> 2² = 4
Power of 4 which is nearest to 3 —> 4¹ = 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. X^K which is closest to arr[i]. Follow the steps:

• Calculate the value of K, which is equal to the floor value of log_x(Y).
• Therefore, K and (K + 1) will be the two integers for which the power could be nearest.   
• Calculate X^K and X^{(K + 1)} and check which is nearer to Y. Then, print that value.

Below is the implementation of the above approach:

Python3

import math    def LOG(x, base):     return int(math.log(x)/math.log(base))    def repbyNP(arr):                  x = arr[-1]             for i in range(len(arr)):                              k = LOG(arr[i], x)         temp = arr[i]                     if abs(x**k - arr[i]) < abs(x**(k + 1) - arr[i]):             arr[i] = x**k         else:             arr[i] = x**(k + 1)                     x = temp             return arr       arr = [2, 4, 6, 3, 11]    print(repbyNP(arr))

Output:

[1, 4, 4, 1, 9]

Time Complexity: O(N)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)