نمایشگرهای GCD برای همه اعداد یک آرایه به جز عناصر موجود در یک محدوده داده شده


سطح دشواری سخت
اغلب در آمازون یکی از سرمایه دی شاو گوگل پی پال Quora داده Teradata
صف برنامه نویسی پویا GCD ریاضی مشکل پرس و جو

بیان مسأله

مسئله "درخواست های GCD برای همه اعداد یک آرایه به جز عناصر موجود در یک محدوده مشخص شده" بیان می کند که به شما یک عدد داده می شود عدد صحیح صف و یک q تعداد سeriesالات هر پرسش شامل عدد چپ و راست است. دستور مسئله می خواهد بزرگترین تقسیم کننده مشترک را در بین تمام اعداد صحیح به استثنای محدوده داده شده از درخواست جستجو کند.

مثال

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 عنصر پسوندArray و عنصر آرایه داده شده را پیدا کرده و GCD را در پسوند Arr ذخیره کنید.
  4. برای هر پرسش داده شده ، اگر محدوده سمت چپ برابر با 0 باشد ، مقدار پسوندArray [راست + 1] را برگردانید.
  5. اگر مقدار راست برابر با n است - 1 ، مقدار preArray را بازگردانید [چپ - 1].
  6. در غیر این صورت مقدار GCD مربوط به preArray [چپ-1] و پسوند Array [راست + 1] را برمی گردانیم.

توضیح

با توجه به آرایه ای از اعداد صحیح و پرس و جو برای پاسخ دادن. از ما خواسته می شود که بزرگترین مقسوم علیه مشترک از اعداد به جز تمام اعداد صحیح در محدوده داده شده از پرس و جو. اگر در یک آرایه از طول 0 دامنه ای از 1 تا 5 به ما داده شود ، این بدان معناست که ما باید بزرگترین تقسیم کننده مشترک را در بین تمام اعداد صحیح به جز arr [0] و arr [1] در یک آرایه پیدا کنیم. پرس و جو با توجه به اینکه شامل چپ و راست به عنوان یک دامنه است. ما باید اعداد صحیحی را که در این محدوده قرار دارند ترک کنیم.

ما می خواهیم آرایه را رد کنیم اما قبل از آن اولین عنصر آرایه داده شده را در اولین عنصر preArray کپی کنید. بعد از آن آرایه را از چپ به راست عبور دهید. در این مدت ما در حال ساخت preArray و پسوند Arrray خواهیم بود. برای preArray بزرگترین تقسیم کننده عنصر در شاخص جریان را در آرایه ورودی اصلی و عنصر را در شاخص قبلی در preArray پیدا کنید. این GCD از این اعداد را در عنصر preArray ذخیره کنید. پس از عبور از آرایه ، پسوند Array را بسازید. برای این کار ، در محل آخرین عنصر پسوند Arrray. آخرین عنصر آرایه عنصر آرایه داده شده را کپی کنید. پس از آن همان روشی را که برای پیش آرایه دنبال می کنیم دنبال می کنیم اما از راست به چپ آرایه.

برای هر پرسش داده شده از دامنه داده شده ، بررسی کنید که آیا محدوده سمت چپ داده شده برابر با 0 است. بنابراین مقدار پسوند Array [راست + 1] را برگردانید. بررسی کنید که آیا مقدار right با طول آرایه برابر است یا خیر. سپس مقدار preArray را بازگردانید [چپ -1]. در غیر اینصورت بزرگترین تقسیم کننده عنصر در نمای چپ در preArray و عنصر در نمای راست در پسوند Array بازگردانده می شوند. این پاسخ مورد نیاز ما خواهد بود.

رمز

کد ++ 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

کد جاوا برای یافتن آرایه 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) جایی که "س" تعداد سeriesالات است و "N”تعداد عناصر موجود در آرایه ورودی است. بر) زمان لازم برای ساخت پیش آرایه و پسوند Arrray لازم است. سپس O (Qlog n) زمان برای پاسخ به سوالات مورد نیاز است زیرا برای پاسخ به هر پرسش ما gcd از دو عدد را پیدا می کنیم که هزینه ورود به سیستم ما در n است که n تعداد است و log با پایه 2 است.

پیچیدگی فضا

پیچیدگی فضا برای حل نمایش داده ها برای GCD برای همه اعداد یک آرایه به جز عناصر در یک محدوده مشخص شده است بر) جایی که "N" تعداد عناصر موجود در آرایه برای ذخیره preArray و پسوند Array است.