通过用给定范围内最远的同质数替换元素来修改数组

原文:https://www . geeksforgeeks . org/通过用给定范围内最远的同素数替换元素来修改数组/

给定一个由 N 个整数和两个正整数 L 和 R 组成的数组arr【】，任务是为每个数组元素找到【L，R】范围内最远的同质数。

示例:

输入: arr[] = {5，150，120}，L = 2，R = 250
输出: 249 7 247
说明:
与 arr[0]同素且离它最远的数是 249。
与 arr[1]同素且离它最远的数是 7。
与 arr[2]同素且离它最远的数是 247。

输入: arr[] = {60，246，75，103，155，110}，L = 2，R = 250
输出: 60 246 75 103 155 110

方法:给定的问题可以通过对每个数组元素迭代给定的范围【L，R】并找到与该数组元素具有 GCD 1 的最远元素来解决。按照以下步骤解决问题:

• 遍历给定数组 arr[] ，并执行以下步骤:
  
  
  • 初始化两个变量，说 d 为 0 和互素为 -1 ，分别用arr【I】存储最远距离和互素数。
  
  
  • 迭代给定的范围【L，R】并执行以下步骤:
    
    
    • 将 d 的值更新为arr【I】和 j 的绝对差值。
    
    
    • 如果arr[I]j的最大公约数为1d小于ABS(arr[I]–j)，则将互质的值更新为 j 。
    
    
    
    
  
  
  • 将 arr[i] 的值更新为互质。
  
  
  
  


• 完成上述步骤后，打印数组 arr[] 作为结果数组。

下面是上述方法的实现:

C++

// C++ program for the above approach
#include
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         // 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                 // 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         cout <}
// 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     {
        // 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             {
                // 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         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


Python 3

# 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                 # 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             // 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                     // 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             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.


java 描述语言

Output: 

247 5 248 250 2 249


时间复杂度:O((R–L)* N)
T3】辅助空间: O(1)