Modify array by replacing elements with their farthest co-prime number from a given range

0 0 6 minutes read

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 b
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
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 < 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 Code
int 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 approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
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++)
        System.out.print(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 Kingash

Python3

# python 3 program for the above approach
from math import gcd
 
# Function to find the farthest
# co-prime number over the range
# [L, R] for each array element
def 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 Code
if __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 approach
using 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 b
function 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 element
function 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 zambiatek!