Given an array arr[] consisting of N integers and two positive integers L and R, the task is to find the farthest co-prime number in the range [L, R] for every array element.
Examples:
Input: arr[] = {5, 150, 120}, L = 2, R = 250
Output: 249 7 247
Explanation:
The number which is co-prime with arr[0] and farthest from it is 249.
The number which is co-prime with arr[1] and farthest from it is 7.
The number which is co-prime with arr[2] and farthest from it is 247.Input: arr[] = {60, 246, 75, 103, 155, 110}, L = 2, R = 250
Output: 60 246 75 103 155 110
Approach: The given problem can be solved by iterating over the given range [L, R] for every array element and find the farthest element from it having GCD 1 with the array element. Follow the steps below to solve the problem:
- Traverse the given array arr[] and perform the following steps:
- Initialize two variables, say d as 0 and coPrime as -1, to store the farthest distance and the number coprime with the arr[i] respectively.
- Iterate over the given range [L, R] and perform the following steps:
- Update the value of d as the absolute difference of arr[i] and j.
- If the greatest common divisor of arr[i] and j is 1 and d is less than abs(arr[i] – j), then update the value of coPrime as j.
- Update the value of arr[i] as the coPrime.
- After completing the above steps, print the array arr[] as the resultant array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate GCD// of the integers a and bint gcd(int a, int b){ // Base Case if (a == 0) return b; // Recursively find the GCD return gcd(b % a, a);}// Function to find the farthest// co-prime number over the range// [L, R] for each array elementvoid update(int arr[], int n){ // Traverse the array arr[] for (int i = 0; i < n; i++) { // Stores the distance // between j and arr[i] int d = 0; // Stores the integer coprime // which is coprime is arr[i] int coPrime = -1; // Traverse the range [2, 250] for (int j = 2; j <= 250; j++) { // If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 && d < abs(arr[i] - j)) { // Update the value of d d = abs(arr[i] - j); // Update the value // of coPrime coPrime = j; } } // Update the value of arr[i] arr[i] = coPrime; } // Print the array arr[] for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver Codeint main(){ int arr[] = { 60, 246, 75, 103, 155, 110 }; int N = sizeof(arr) / sizeof(arr[0]); update(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to calculate GCD// of the integers a and bstatic int gcd(int a, int b){ // Base Case if (a == 0) return b; // Recursively find the GCD return gcd(b % a, a);}// Function to find the farthest// co-prime number over the range// [L, R] for each array elementstatic void update(int arr[], int n){ // Traverse the array arr[] for(int i = 0; i < n; i++) { // Stores the distance // between j and arr[i] int d = 0; // Stores the integer coprime // which is coprime is arr[i] int coPrime = -1; // Traverse the range [2, 250] for(int j = 2; j <= 250; j++) { // If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 && d < Math.abs(arr[i] - j)) { // Update the value of d d = Math.abs(arr[i] - j); // Update the value // of coPrime coPrime = j; } } // Update the value of arr[i] arr[i] = coPrime; } // Print the array arr[] for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");}// Driver Codepublic static void main(String[] args){ int arr[] = { 60, 246, 75, 103, 155, 110 }; int N = arr.length; update(arr, N);}}// This code is contributed by Kingash |
Python3
# python 3 program for the above approachfrom math import gcd# Function to find the farthest# co-prime number over the range# [L, R] for each array elementdef update(arr, n): # Traverse the array arr[] for i in range(n): # Stores the distance # between j and arr[i] d = 0 # Stores the integer coprime # which is coprime is arr[i] coPrime = -1 # Traverse the range [2, 250] for j in range(2, 251, 1): # If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 and d < abs(arr[i] - j)): # Update the value of d d = abs(arr[i] - j) # Update the value # of coPrime coPrime = j # Update the value of arr[i] arr[i] = coPrime # Print the array arr[] for i in range(n): print(arr[i],end =" ")# Driver Codeif __name__ == '__main__': arr = [60, 246, 75, 103, 155, 110] N = len(arr) update(arr, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG { // Function to calculate GCD // of the integers a and b static int gcd(int a, int b) { // Base Case if (a == 0) return b; // Recursively find the GCD return gcd(b % a, a); } // Function to find the farthest // co-prime number over the range // [L, R] for each array element static void update(int[] arr, int n) { // Traverse the array arr[] for (int i = 0; i < n; i++) { // Stores the distance // between j and arr[i] int d = 0; // Stores the integer coprime // which is coprime is arr[i] int coPrime = -1; // Traverse the range [2, 250] for (int j = 2; j <= 250; j++) { // If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 && d < Math.Abs(arr[i] - j)) { // Update the value of d d = Math.Abs(arr[i] - j); // Update the value // of coPrime coPrime = j; } } // Update the value of arr[i] arr[i] = coPrime; } // Print the array arr[] for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Driver Code public static void Main(string[] args) { int[] arr = { 60, 246, 75, 103, 155, 110 }; int N = arr.Length; update(arr, N); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program to implement// the above approach// Function to calculate GCD// of the integers a and bfunction gcd(a, b){ // Base Case if (a == 0) return b; // Recursively find the GCD return gcd(b % a, a);} // Function to find the farthest// co-prime number over the range// [L, R] for each array elementfunction update(arr, n){ // Traverse the array arr[] for(let i = 0; i < n; i++) { // Stores the distance // between j and arr[i] let d = 0; // Stores the integer coprime // which is coprime is arr[i] let coPrime = -1; // Traverse the range [2, 250] for(let j = 2; j <= 250; j++) { // If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 && d < Math.abs(arr[i] - j)) { // Update the value of d d = Math.abs(arr[i] - j); // Update the value // of coPrime coPrime = j; } } // Update the value of arr[i] arr[i] = coPrime; } // Print the array arr[] for(let i = 0; i < n; i++) document.write(arr[i] + " ");}// Driver code let arr = [ 60, 246, 75, 103, 155, 110 ]; let N = arr.length; update(arr, N) </script> |
Output:
247 5 248 250 2 249
Time Complexity: O((R – L) * 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!
