Дархостҳо барои GCD оид ба ҳамаи рақамҳои массив, ба истиснои элементҳои диапазони додашуда


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Пойтахт Яке аз DE Шо Google PayPal Quora Терадата
тартиботи ҳарбӣ Барномарезии динамикӣ 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-ро дар пасвандиArray нигоҳ доред.
  4. Барои ҳар як дархости додашуда, агар диапазони чап ба 0 баробар бошад, пас арзиши суффиксиArray [right + 1] -ро баргардонед.
  5. Дигар агар арзиши рост ба n - 1 баробар бошад, пас арзиши preArray [чап - 1] -ро баргардонед.
  6. Дигар арзиши GCD-и preArray [left-1] ва суффиксиArray [рост + 1] -ро бармегардонад.

Шарҳ

Бо назардошти массиви бутун ва саволҳо барои посух додан. Аз мо хоҳиш карда мешавад, ки фаҳмидани бузургтарин тақсимкунандаи умумӣ аз рақамҳо, ба истиснои тамоми бутунҳо дар доираи додашудаи дархост. Агар ба мо дар массиви дарозии 0 диапазони аз 1 то 5 дода шавад, ин маънои онро дорад, ки мо бояд бузургтарин тақсимкунандаи умумии тамоми ададҳоро, ба истиснои arr [0] ва arr [1] -и массивро ёбем. Дархости додашуда, ки чап ва ростро ҳамчун диапазон дар бар мегирад. Мо бояд ададҳои бутунеро, ки дар ин диапазон омадаанд, гузорем.

Мо массивро тай карданием, аммо пеш аз он, унсури якуми массиви додашударо ба унсури якуми preArray нусхабардорӣ кунед. Пас аз он массивро аз чап ба рост тай кунед. Дар ин муддат мо preArray ва suffixArray месозем. Барои preArray бузургтарин тақсимкунандаи умумии элементро дар индекси ҷорӣ дар массиви аслии вуруд ва унсури индекси қаблиро дар preArray дарёфт кунед. Ин GCD ин рақамҳоро дар унсури preArray нигоҳ доред. Пас аз гардиши массив, пасвандиArray созед. Барои ин, дар ҷои унсури охирини пасвандиArray. Унсури охирини массиви унсури массиви додашударо нусхабардорӣ кунед. Пас аз он, ҳамон амалеро иҷро кунед, ки мо барои preArray амал мекунем, аммо аз рост ба чапи массив.

Барои ҳар як дархости диапазони додашуда, санҷед, ки диапазони чапи додашуда ба 0 баробар аст. Ҳамин тариқ арзиши суффиксиArray [right + 1] -ро баргардонед. Санҷед, ки оё арзиши рост ба дарозии массив баробар аст. Пас арзиши 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 вақт лозим аст. Баъд О (Qlog n) барои посух додан ба саволҳо вақт талаб карда мешавад, зеро барои посух додани ҳар як савол мо gcd ду рақамеро ёфта истодаем, ки ба мо log n, ки n рақам аст ва log бо пойгоҳи 2 аст.

Мураккабии фазо

Мураккабии фосила барои ҳалли дархостҳо барои GCD ҳамаи рақамҳои массив, ба истиснои элементҳои диапазони додашуда, мебошад О (Н) ки дар "N" шумораи унсурҳои массив барои нигоҳдории preArray ва suffixArray мебошад.