Given an array arr[] consisting of N positive integers, the task is to replace each array element with the nearest power of GCD of all the preceding array elements. If there exists more than one possible answer, then print any one of them.
Examples:
Input: arr[] = {4, 2, 8, 2}
Output: 4 1 8 2
Explanation:
For element arr[0], the element remains the same.
For element arr[1], the GCD of preceding elements is 4. The power of 4 which is nearest to 2 is 1.
For element arr[2], the GCD of preceding elements is 2. The power of 2 which is nearest to 8 is 8.
For element arr[3], the GCD of preceding elements is 2. The power of 2 which is nearest to 2 is 2.
Hence, the modified array becomes {4, 1, 8, 2}.Input: arr[] = {3, 6, 9, 2}
Output: 3 9 9 3
Approach: The given problem can be solved by calculating prefix GCD and then finding the nearest power of that GCD which is closest to the current element, for each array element. Below are some observations:
- For calculating the power of X which is closest to Y, the idea is to get the value of K such that the absolute difference between XK and Y is minimum.
- For finding the value of K, find the floor value of logx(Y).
- Therefore, K and (K + 1) will be the two integers for which the nearest power can be a possible value.
Follow the steps below to solve the problem:
- Initialize a variable, say prefixGCD with arr[0], to store the prefix GCD till each index of the array.
- Traverse the given array arr[] over the range of indices [1, N] and perform the following steps:
- Find the floor value of logprefixGCD(arr[i]), say K.
- Find the value of (arr[i]K) and (arr[i]K + 1) and check which is closest to arr[i] and assign that value to the current index of the array.
- Update prefixGCD as the gcd of prefixGCD and arr[i].
- After completing the above steps, print the modified array.
Below is the implementation of the above approach:
C++
// CPP program for the above approach#include<bits/stdc++.h>using namespace std;// Function to find the float// value of log functionint log1(int x, int base){ return int(log(x) / log(base));}// Function for finding the nearest// power of X with respect to Yint getNP(int x, int y){ // Base Case if (y == 1) return 1; // Find the value of K int k = int(log1(x, y)); // Nearest power of GCD closest to Y if (abs(pow(y, k) - x) < abs(pow(y, (k + 1)) - x)) return pow(y, k); return pow(y, (k + 1));}// Function to modify the given array// such that each array element is the// nearest power of X with respect to Yvector<int> modifyEle(vector<int> arr){ int prevGCD = arr[0]; // Traverse the array for (int i = 1; i < arr.size(); i++) { // Find the current number int NP = getNP(arr[i], prevGCD); // Update the GCD prevGCD = __gcd(arr[i], prevGCD); // Update the array at the // current index arr[i] = NP; } // Return the updated GCD array return arr;}// Driver Codeint main(){ vector<int>arr{4, 2, 8, 2}; // Function Call vector<int> ans = modifyEle(arr); cout<<"["; for(int i = 0; i < ans.size(); i++) if(i < ans.size() - 1) cout << ans[i] << ", "; else cout << ans[i]; cout << "]";}// This code is contributed by SURENDRA_GANGWAR. |
Java
// Java program for the above approachimport java.util.*;class GFG{ // gcd static int gcd(int x, int y) { if (x == 0) return y; return gcd(y % x, x); } // Function to find the float // value of log function static int log1(int x, int b) { return (int)(Math.log(x) / Math.log(b)); } // Function for finding the nearest // power of X with respect to Y static int getNP(int x, int y) { // Base Case if (y == 1) return 1; // Find the value of K int k = (int)(log1(x, y)); // Nearest power of GCD closest to Y if (Math.abs(Math.pow(y, k) - x) < Math.abs(Math.pow(y, (k + 1)) - x)) return (int)(Math.pow(y, k)); return (int)(Math.pow(y, (k + 1))); } // Function to modify the given array // such that each array element is the // nearest power of X with respect to Y static ArrayList<Integer> modifyEle(ArrayList<Integer> arr) { int prevGCD = arr.get(0); // Traverse the array for (int i = 1; i < arr.size(); i++) { // Find the current number int NP = getNP(arr.get(i), prevGCD); // Update the GCD prevGCD = gcd(arr.get(i), prevGCD); // Update the array at the // current index arr.set(i, NP); } // Return the updated GCD array return arr; }// Driver Codepublic static void main(String[] args){ ArrayList<Integer> arr = new ArrayList<Integer>() ; arr.add(4); arr.add(2); arr.add(8); arr.add(2); // Function Call ArrayList<Integer> ans = new ArrayList<Integer>(); ans = modifyEle(arr); System.out.print("["); for (int i = 0; i < ans.size(); i++) if (i < ans.size() - 1) System.out.print(ans.get(i) + ", "); else System.out.print(ans.get(i)); System.out.print("]");}}// This code is contributed by susmitakundugoaldanga. |
Python3
# Python program for the above approachimport math# Function to find the float# value of log functiondef LOG(x, base): return int(math.log(x)/math.log(base))# Function for finding the nearest# power of X with respect to Ydef getNP(x, y): # Base Case if y == 1: return 1 # Find the value of K k = int(math.log(x, y)) # Nearest power of GCD closest to Y if abs(y**k - x) < abs(y**(k + 1) - x): return y**k return y**(k + 1)# Function to find the GCD of a and bdef GCD(a, b): # Base Case if b == 0: return a # Recursively calculate GCD return GCD(b, a % b)# Function to modify the given array# such that each array element is the# nearest power of X with respect to Ydef modifyEle(arr): # Stores the prefix GCD prevGCD = arr[0] # Traverse the array for i in range(1, len(arr)): # Find the current number NP = getNP(arr[i], prevGCD) # Update the GCD prevGCD = GCD(arr[i], prevGCD) # Update the array at the # current index arr[i] = NP # Return the updated GCD array return arr# Driver Codearr = [4, 2, 8, 2]# Function Callprint(modifyEle(arr)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // gcd static int gcd(int x, int y) { if (x == 0) return y; return gcd(y % x, x); } // Function to find the float // value of log function static int log1(int x, int b) { return (int)(Math.Log(x) / Math.Log(b)); } // Function for finding the nearest // power of X with respect to Y static int getNP(int x, int y) { // Base Case if (y == 1) return 1; // Find the value of K int k = (int)(log1(x, y)); // Nearest power of GCD closest to Y if (Math.Abs(Math.Pow(y, k) - x) < Math.Abs(Math.Pow(y, (k + 1)) - x)) return (int)(Math.Pow(y, k)); return (int)(Math.Pow(y, (k + 1))); } // Function to modify the given array // such that each array element is the // nearest power of X with respect to Y static List<int> modifyEle(List<int> arr) { int prevGCD = arr[0]; // Traverse the array for (int i = 1; i < arr.Count; i++) { // Find the current number int NP = getNP(arr[i], prevGCD); // Update the GCD prevGCD = gcd(arr[i], prevGCD); // Update the array at the // current index arr[i] = NP; } // Return the updated GCD array return arr; } // Driver Code public static void Main(string[] args) { List<int> arr = new List<int>() { 4, 2, 8, 2 }; // Function Call List<int> ans = new List<int>(); ans = modifyEle(arr); Console.Write("["); for (int i = 0; i < ans.Count; i++) if (i < ans.Count - 1) Console.Write(ans[i] + ", "); else Console.Write(ans[i]); Console.Write("]"); }}// This code is contributed by chitranayal. |
Javascript
<script> // JavaScript program for the above approach // gcd function gcd(x, y) { if (x === 0) return y; return gcd(y % x, x); } // Function to find the float // value of log function function log1(x, b) { return parseInt(Math.log(x) / Math.log(b)); } // Function for finding the nearest // power of X with respect to Y function getNP(x, y) { // Base Case if (y === 1) return 1; // Find the value of K var k = parseInt(log1(x, y)); // Nearest power of GCD closest to Y if (Math.abs(Math.pow(y, k) - x) < Math.abs(Math.pow(y, k + 1) - x)) return parseInt(Math.pow(y, k)); return parseInt(Math.pow(y, k + 1)); } // Function to modify the given array // such that each array element is the // nearest power of X with respect to Y function modifyEle(arr) { var prevGCD = arr[0]; // Traverse the array for (var i = 1; i < arr.length; i++) { // Find the current number var NP = getNP(arr[i], prevGCD); // Update the GCD prevGCD = gcd(arr[i], prevGCD); // Update the array at the // current index arr[i] = NP; } // Return the updated GCD array return arr; } // Driver Code var arr = [4, 2, 8, 2]; // Function Call var ans = []; ans = modifyEle(arr); document.write("["); for (var i = 0; i < ans.length; i++) if (i < ans.length - 1) document.write(ans[i] + ", "); else document.write(ans[i]); document.write("]");</script> |
Output:
[4, 1, 8, 2]
Time Complexity: O(N*log(M)), where M is the maximum element of the array.
Auxiliary Space: O(1)
