Упити за децималне вредности поднизова бинарног низа


Ниво тешкоће Средњи
Често питани у амазонка гоогле
Ред Куери Проблем

Напишите упите за децималне вредности поднизова бинарног низа у датом бинарном низу. Изјава о проблему тражи откривање децималног броја тако формираног помоћу опсега у бинарном низу.

Пример

Улаз:

арр [] = {1, 0, 1, 1, 0, 0, 1, 1}

Упит (1, 5)

Упит (3, 6)

Излаз:

12 9

objašnjenje:

Излаз тако формиран као бинарни бројеви који представљају у распону од 1 до 5 укључујући (01100), је 12.

Излаз тако формиран као бинарни бројеви представља у распону од 3 до 6 закључно (1001), је 9.

Упити за децималне вредности поднизова бинарног низа

 

Алгоритам за упите за децималне вредности поднизова бинарног низа

  1. Креирајте низ као префикАрраи, иницијализујте га са 0.
  2. Копирајте последњи елемент префикАрраи у последњи елемент поредак дато.
  3. Пређите низом здесна налево од низа и сачувајте производ датог елемента низа и потенцијале 2 и додајте га са префикАрраи.
  4. Добијте упит, ако вредност десно није једнака последњој вредности индекса датог низа, вратите поделу разлике префикАрраи [лево] и префикАрраи [десно + 1] и операцију померања 1 и десно индекс низа.
  5. Иначе враћају поделу префикАрраи [лево] и операцију померања индекса 1 и десног низа.

Објашњење за упите за децималне вредности поднизова бинарног низа

У вези са проблемом Упити за децималне вредности поднизова бинарног низа, дати а бинарни низ и опсег индекса као леви и десни индекс. Пронађите децимални облик датог бинарног броја тако формираног са датим опсегом. Даћемо упит у коме смо дали опсег. Морамо пронаћи децимални број тако формиран од бинарног броја са опсегом. За ово ћемо створити додатни низ величине исте дужине низа. Изградићемо тај низ или можемо рећи да можемо унапред да обрадимо тај низ и попунимо неке вредности у њему како бисмо могли да решимо упит у константном времену.

Пређите низом, али пре него што пређете низ, напуните низ са 0. У јави када се низ креира аутоматски се попуњава са 0, али у Ц ++-у то морамо сами. Након тога, узмите производ последњег елемента низа и 1, сачувајте вредност у последњем елементу префикАрраи. Сада почните с десна на лево, значи почињете од 2nd последњи елемент низа, сада узмите производ бројева у степенима 2 и датог елемента низа и додајте га са претходном вредношћу префикАрраи. Наставите да га додајете са вредностима префикАрраи и чувајте на одговарајућем месту префикАрраи.

За сваки упит који нам је дат, проверите да ли дата вредност није једнака последњем индексу низа. Ако се утврди да је тачно, узмите разлику префикАрраи [лево] и префикАрраи [десно] и поделите је са вредношћу која је тако формирана када применимо операцију померања у степенима 2 и вратимо ту вредност, у супротном једноставно вратимо разлику од префикАрраи [лево] и поделите га операцијом померања на десну вредност и вратите.

Имплементација

Ц ++ програм

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>

using namespace std;

void buildArray(int arr[], int n, int prefixArray[])
{
    memset(prefixArray, 0, n * sizeof(int));
    prefixArray[n - 1] = arr[n - 1] * pow(2, 0);
    for (int i = n - 2; i >= 0; i--)
        prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
}
int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
{
    if (right!= n - 1)
        return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));

    return prefixArray[left] / (1 << (n - 1 - right));
}
int main()
{
    int arr[] = {1, 0, 1, 1, 0, 0, 1, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    int prefixArray[n];
    buildArray(arr, n, prefixArray);
    cout << getDeimalNum(arr, 1, 5, n, prefixArray) << endl;
    cout << getDeimalNum(arr, 3, 6, n, prefixArray) << endl;
    return 0;
}
12
9

Јава програм

import java.util.Arrays;

class DecimalfromSubArray
{
    static void buildArray(int arr[], int n, int prefixArray[])
    {
        Arrays.fill(prefixArray, 0);
        prefixArray[n - 1] = arr[n - 1] * (int)(Math.pow(2, 0));
        for (int i = n - 2; i >= 0; i--)
        {
            prefixArray[i] = prefixArray[i + 1] + arr[i] * (1 << (n - 1 - i));
        }
    }
    
    static int getDeimalNum(int arr[], int left, int right, int n, int prefixArray[])
    {
        if (right != n - 1)
        {
            return (prefixArray[left] - prefixArray[right + 1]) / (1 << (n - 1 - right));
        }
        return prefixArray[left] / (1 << (n - 1 - right));
    }
    
    public static void main(String[] args)
    {
        int arr[] = {1, 0, 1, 1, 0, 0, 1, 1};
        int n = arr.length;

        int prefixArray[] = new int[n];
        buildArray(arr, n, prefixArray);

        System.out.println(getDeimalNum(arr,1, 5, n, prefixArray));

        System.out.println(getDeimalNum(arr,3, 6, n, prefixArray));
    }
}
12
9

Анализа сложености упита за децималне вредности поднизова бинарног низа

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

О (к) где "К" је број упита.

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

Он) где „Н“ је број елемената у низу.

Препорука