बायनरी अ‍ॅरेच्या सबब्रेच्या दशांश मूल्यांसाठी क्वेरी  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन Google
अरे क्वेरी समस्या

दिलेल्या बायनरी अ‍ॅरेमध्ये बायनरी अ‍ॅरेच्या सबरीच्या दशांश मूल्यांसाठी क्वेरी लिहा. समस्या विधान बायनरी अ‍ॅरेमधील श्रेणीच्या मदतीने तयार केलेली दशांश संख्या शोधण्यास सांगते.

उदाहरण  

इनपुट:

अरे [] = {1, 0, 1, 1, 0, 0, 1, 1}

क्वेरी (1, 5)

क्वेरी (3, 6)

आउटपुट:

12 9

स्पष्टीकरण:

1 ते 5 समावेशक (01100) च्या श्रेणीत बायनरी क्रमांक दर्शविणारे आउटपुट 12 आहे.

आउटपुट म्हणून तयार बायनरी क्रमांक 3 ते 6 समावेशक (1001) च्या श्रेणीमध्ये प्रतिनिधित्व करणे 9 आहे.

बायनरी अ‍ॅरेच्या सबरीच्या दशांश मूल्यांसाठी क्वेरीपिन

 

बायनरी अ‍ॅरेच्या सबरीच्या दशांश मूल्यांसाठी क्वेरींसाठी अल्गोरिदम  

  1. उपसर्गअरे म्हणून एक अ‍ॅरे बनवा, 0 ने प्रारंभ करा.
  2. उपसर्ग आरेचा शेवटचा घटक शेवटच्या घटकावर कॉपी करा अॅरे दिले.
  3. अ‍ॅरेच्या डावीकडून डावीकडील अ‍ॅरेमधून जा आणि दिलेल्या अ‍ॅरे घटकाचे उत्पादन आणि 2 ची शक्ती संचयित करा आणि त्यास प्रत्यय अ‍ॅरेसह जोडा.
  4. क्वेरी मिळवा, दिलेली अ‍ॅरेच्या शेवटच्या निर्देशांकाच्या मूल्याइतकी व्हॅल्यू बरोबर नसल्यास, उपसर्ग एर्रे [डावे] आणि उपसर्गअरे [उजवे + 1] मधील फरक आणि 1 आणि उजवीकडे शिफ्ट ऑपरेशन परत करा. अ‍ॅरेची अनुक्रमणिका.
  5. अन्यथा उपसर्ग एरे [डावे] आणि 1 मधील शिफ्ट ऑपरेशन आणि अ‍ॅरेचा उजवा अनुक्रमणिका परत करा.
हे सुद्धा पहा
डिकोड स्ट्रिंग

बायनरी अ‍ॅरेच्या सबरीच्या दशांश मूल्यांसाठी क्वेरींसाठी स्पष्टीकरण  

समस्येसंदर्भात, बायनरी अ‍ॅरेच्या सबर्रेच्या दशांश मूल्यांसाठी क्वेरी, दिलेल्या अ बायनरी अ‍ॅरे डावे अनुक्रमणिका आणि उजवे अनुक्रमणिका म्हणून अनुक्रमणिकेची श्रेणी. दिलेल्या श्रेणीसह तयार केलेल्या दिलेल्या बायनरी संख्येचा दशांश फॉर्म शोधा. आम्हाला एक क्वेरी दिली जाईल ज्यामध्ये आम्ही एक श्रेणी दिली आहे. श्रेणीसह बायनरी क्रमांकाची तयार केलेली दशांश संख्या आपल्याला शोधावी लागेल. त्यासाठी theरेच्या लांबीइतकेच आकाराचा अतिरिक्त अ‍ॅरे तयार करणार आहोत. आपण त्या अ‍ॅरेची उभारणी करू किंवा आम्ही असे म्हणू शकतो की arरेची पूर्वपूर्ती करू शकतो आणि त्यात काही व्हॅल्यूज भरू जेणेकरून आम्ही निरंतर वेळेत क्वेरीचे निराकरण करू.

अ‍ॅरेमधून जा, परंतु अ‍ॅरे ट्रॅव्हर्स् करण्यापूर्वी, अ‍ॅरे 0 सह भरा. जावा मध्ये जेव्हा अ‍ॅरे तयार होईल तेव्हा ते स्वयंचलितपणे 0 ने भरला जाईल, परंतु सी ++ मध्ये आपल्याला ते स्वतः करावे लागेल. त्यानंतर, अंतिम अ‍ॅरे घटक आणि 1 चे उत्पादन मिळवा, उपसर्ग एर्रेच्या अंतिम घटकामधील मूल्य जतन करा. आता उजवीकडून डावीकडे प्रारंभ करा म्हणजे 2 पासून प्रारंभ कराnd अ‍ॅरेचा शेवटचा घटक, आता २ च्या संख्येची संख्या आणि दिलेल्या अ‍ॅरे एलिमेंटस मिळवा आणि त्यास प्रीफिक्सएरेच्या मागील मूल्यासह जोडा. त्यास उपसर्ग अ‍ॅरेच्या मूल्यांसह जोडा आणि त्यास उपसर्ग अ‍ॅरेच्या संबंधित ठिकाणी संचयित करा.

हे सुद्धा पहा
दिलेल्या श्रेणीतील मूल्यांसह अ‍ॅरे घटकांच्या संख्येसाठी क्वेरी

आम्हाला दिलेल्या प्रत्येक क्वेरीसाठी, दिलेली योग्य व्हॅल्यू अ‍ॅरेच्या शेवटच्या इंडेक्सइतकी नाही की नाही ते तपासा. जर ते खरे असल्याचे आढळले तर फरक उपसर्ग अ‍ॅरे [डावे] आणि उपसर्ग अ‍ॅरे [उजवीकडे] मिळवा आणि जेव्हा आपण २ च्या शक्तींमध्ये शिफ्ट ऑपरेशन लागू करतो तेव्हा तयार केलेल्या मूल्यासह विभाजित करा आणि ते मूल्य परत करा, अन्यथा फक्त फरक परत करा. प्रीफिक्सअरे [डावीकडे] आणि उजव्या व्हॅल्यूवर शिफ्ट ऑपरेशनसह विभाजित करा आणि ते परत करा.

अंमलबजावणी  

सी ++ प्रोग्राम

#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

बायनरी ofरेच्या सबब्रेच्या दशांश मूल्यांसाठी क्वेरींसाठी जटिलता विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (प्र) जेथे "Q" क्वेरींची संख्या आहे.

हे सुद्धा पहा
समाविष्ट क्रमवारी लावा

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.

संदर्भ