Заявки за GCD на всички номера на масив с изключение на елементи в даден диапазон


Ниво на трудност Трудно
Често задавани в Амазонка Capital One DE Шоу Google PayPal Quora Терадата
Array Динамично програмиране GCD Математически Задача за заявка

Декларация за проблема

Проблемът „Заявки за GCD на всички номера на масив с изключение на елементи в даден диапазон“ гласи, че ще ви бъде дадено цяло число масив и q брой заявки. Всяка заявка съдържа номера наляво и надясно. Изложението на проблема иска да открие най-големия общ делител на всички цели числа, с изключение на дадения диапазон на заявката.

Пример

arr[] = {1, 3, 6, 9}
Query: {(2, 3), (0, 1), (1, 2)}
1 3 1

Обяснение

GCD на елементите, с изключение на елементи от индекс 2 до 3, т.е. GCD от 1 и 3 е 1

Сега GCD на елементите, с изключение на елементи от индекс 0 до 1, т.е. GCD от 6 и 9 е 3

Отново GCD на елементите, с изключение на елементи от индекс 1 до 2, т.е. GCD от 1 и 9 е 1

Заявки за GCD на всички номера на масив с изключение на елементи в даден диапазон

 

алгоритъм

  1. Създайте два масива с размер, същия като този на дадения входен масив.
  2. Преминете масива от 1 индекс към дължината на масива. След това открийте GCD на текущия елемент и елемент, съхранен в предишния индекс в preArray и го съхранявайте в текущия индекс в preArray.
  3. Прекосете масива отдясно наляво и открийте GCD на елемента suffixArray и дадения елемент на масив и съхранявайте GCD в suffixArray.
  4. За всяка дадена заявка, ако лявият диапазон е равен на 0, връща стойността на suffixArray [вдясно + 1].
  5. В противен случай, ако стойността на right е равна на n - 1, тогава връща стойността на preArray [ляво - 1].
  6. В противен случай връща стойността на GCD на preArray [ляво-1] и суфиксаArray [дясно + 1].

Обяснение

Даден масив от цели числа и заявки за отговор. Ние сме помолени да разберем най-голям общ делител от числата, с изключение на всички цели числа в дадения диапазон на заявката. Ако ни бъде даден диапазон от 0 до 1 в масив с дължина 5. Това означава, че трябва да открием най-големия общ делител на всички цели числа с изключение на arr [0] и arr [1] в масив. Дадена заявка, която съдържа ляво и дясно като диапазон. Трябва да оставим целите числа, които идват в този диапазон.

Ще преминем през масива, но преди това копираме първия елемент от дадения масив в първия елемент на preArray. След това преместете масива отляво надясно. През това време ще изграждаме preArray и суфиксArray. За preArray открийте най-големия общ делител на елемент в текущия индекс в оригиналния входен масив и елемент в предишния индекс в preArray. Съхранявайте този GCD от тези числа в елемента preArray. След обхождането на масива, изградете суфиксаArray. За това на мястото на последния елемент от суфикса Array. Копирайте последния елемент от масива на дадения елемент. След това следвайте същата процедура, както ние следваме за preArray, но отдясно наляво на масива.

За всяка дадена заявка от дадения диапазон проверете дали даден ляв диапазон е равен на 0. По този начин върнете стойността на suffixArray [вдясно + 1]. Проверете дали стойността на right е равна на дължината на масива. След това върнете стойността на preArray [ляво -1]. В противен случай връща най-големия общ делител на елемента в левия индекс в preArray и елемент в десния индекс в suffixArray. Това ще бъде нашият задължителен отговор.

код

C ++ код за намиране на GCD на масив с изключение на даден диапазон

#include<iostream>

using namespace std;
int __GCD(int a, int b)
{
    if (b == 0)
        return a;

    return __GCD(b, a % b);
}

void buildArrayOfGCD(int PreArray[], int arr[], int suffixArray[], int n)
{
    PreArray[0] = arr[0];
    for (int i=1 ; i<n; i++)
        PreArray[i] = __GCD(PreArray[i-1], arr[i]);

    suffixArray[n-1] = arr[n-1];

    for (int i=n-2; i>=0 ; i--)
        suffixArray[i] = __GCD(suffixArray[i+1], arr[i]);
}

int getGCDInRange(int l, int r, int PreArray[], int suffixArray[], int n)
{
    if (l==0)
        return suffixArray[r+1];

    if (r==n-1)
        return PreArray[l-1];
    return __GCD(PreArray[l-1], suffixArray[r+1]);
}

int main()
{
    int arr[] = {1, 3, 6, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int PreArray[n], suffixArray[n];
    buildArrayOfGCD(PreArray, arr, suffixArray, n);

    int l = 2, r = 3;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 0 ;
    r = 1;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    l = 1 ;
    r = 2;
    cout << getGCDInRange(l, r, PreArray, suffixArray, n)
         << endl;
    return 0;
}
1
3
1

Java код за намиране на GCD на масив с изключение на даден диапазон

import java.util.*;

class GCDNumbers
{
    static int GCD(int a, int b)
    {
        if (b == 0)
            return a;

        return GCD(b, a % b);
    }
    
    static void buildArrayOfGCD(int preArray[],int arr[], int suffixArray[], int n)
    {
        preArray[0] = arr[0];

        for (int i = 1; i < n; i++)
            preArray[i] = GCD(preArray[i - 1], arr[i]);

        suffixArray[n - 1] = arr[n - 1];

        for (int i = n - 2; i >= 0; i--)
            suffixArray[i] = GCD(suffixArray[i + 1], arr[i]);
    }

    static int getGCDInRange(int l, int r, int preArray[], int suffixArray[], int n)
    {

        if (l == 0)
            return suffixArray[r + 1];

        if (r == n - 1)
            return preArray[l - 1];

        return GCD(preArray[l - 1], suffixArray[r + 1]);
    }
    
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 6, 9};
        int n = arr.length;
        int preArray[] = new int[n];
        int suffixArray[] = new int[n];
        buildArrayOfGCD(preArray, arr, suffixArray, n);

        int l = 2, r = 3;
        System.out.println(getGCDInRange(l, r, preArray, suffixArray, n));

        l = 0;
        r = 1;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));

        l = 1;
        r = 2;
        System.out.println(getGCDInRange
                           (l, r, preArray, suffixArray, n));
    }
}
1
3
1

Анализ на сложността

Сложност във времето

O (N + Qlogn) където "Q" е броят на заявките и „N”Е броят на елементите във входния масив. НА) изисква се време за изграждане на preArray и suffixArray. Тогава O (Qlog n) за отговор на запитванията е необходимо време, тъй като за отговор на всяка заявка намираме gcd от две числа, което ни струва log n, където n е номерът, а log е с база 2.

Сложност на пространството

Сложността на пространството за решаване на заявки за GCD на всички номера на масив с изключение на елементи в даден диапазон е НА) където "Н" е броят на елементите в масива за съхраняване на preArray и suffixArray.