बाइनरी एर्रेको सबब्रेयसको दशमलव मानहरूको लागि प्रश्नहरू


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन गुगल
एरे प्रश्न समस्या

दिईएको बाइनरी एर्रेमा बाइनरी एर्रेको सबारीको दशमलव मानहरूको लागि प्रश्नहरू लेख्नुहोस्। समस्या कथनले दशमलव नम्बर पत्ता लगाउन सोच्दछ जब बाइनरी एर्रेमा दायराको सहयोगमा गठन गरिएको।

उदाहरणका

इनपुट:

एर [] = {१,,,,, २,,,,,,,}}

प्रश्न (१,))

प्रश्न (१,))

उत्पादन:

12 9

व्याख्या:

1 देखि inc समावेशी (०११००) को दायरा भित्र प्रतिनिधित्व गर्ने बाइनरी संख्याहरूको रूपमा निर्मित आउटपुट १२ हो।

आउटपुट यस रूपमा गठन भयो बाइनरी संख्या to देखि inc समावेशी (१००१) को दायरा भित्र प्रतिनिधित्व गर्दै, is हो।

बाइनरी एर्रेको सबारीको दशमलव मानहरूको लागि प्रश्नहरू

 

बाइनरी एर्रेको सबारीको दशमलव मानहरूको लागि क्वेरीहरूको लागि एल्गोरिथ्म

  1. उपसर्ग एर्रेको रूपमा एर्रे सिर्जना गर्नुहोस्, ० बाट सुरु गर्नुहोस्।
  2. उपसर्ग एर्रेको अन्तिम तत्वको अन्तिम तत्वमा प्रतिलिपि गर्नुहोस् array दिईयो।
  3. एर्रेको दायाँ देखि बाँया एर्रेको माध्यमबाट पार गर्नुहोस्, र दिइएको एर्रे एलिमेन्टको गुण र २ को शक्तिको भण्डार गर्नुहोस्, र उपसर्ग एरेसँग यसलाई थप्नुहोस्।
  4. क्वेरी पाउनुहोस्, यदि मान दायाँ दिइएको एर्रेको अन्तिम अनुक्रमणिका मानसँग बराबर छैन भने, उपसर्ग एर्रे [बायाँ] र उपसर्ग एर्रे [दायाँ + १] को भिन्नता र १ र दाईको सिफ्ट आपरेशन फिर्ता गर्नुहोस्। एर्रेको सूचकांक।
  5. अन्यथा उपसर्ग एर्रेको बाँकी भाग [बाँया] र १ को सिफ्ट अपरेशन र एर्रेको दाँया अनुक्रमणिका।

बाइनरी एर्रेको सबारीको दशमलव मानहरूको लागि प्रश्नहरूको लागि स्पष्टीकरण

समस्याको सन्दर्भमा बाइनरी एर्रेको सबारीको दशमलव मानहरूको लागि प्रश्नहरू बाइनरी एर्रे बायाँ अनुक्रमणिका र दाँया अनुक्रमणिकाको रूपमा अनुक्रमणिकाको दायरा। दिइएको बाइनरी नम्बरको दशमलव फारम फेला पार्नुहोस् यसरी दिइएको दायरासँग बनाइएको छ। हामीलाई क्वेरी दिइनेछ जसमा हामीले दायरा दियौं। हामीले दशमलव नम्बर फेला पार्नु पर्दछ जुन दायराको साथ बाइनरी नम्बरको गठन गर्दछ। यसको लागि हामी आकारको थप एर्रे सिर्जना गर्ने छौं एरेको लम्बाई जत्तिकै। हामी त्यो एर्रे निर्माण गर्दैछौं वा हामी भन्न सक्दछौं कि हामी प्रिअ्रोसेस गर्न सक्छौं कि एरे र यसमा केही मानहरू भर्दछौं ताकि हामी क्वेरीलाई स्थिर समयमा समाधान गर्न सक्दछौं।

एर्रेको माध्यम बाट जानुहोस्, तर एर्रे ट्र्याभ्रेस गर्नु अघि एरेलाई ० भर्न त्यस पछि, अन्तिम एर्रे एलिमेन्टको उत्पाद प्राप्त गर्नुहोस् र १, उपसर्ग एर्रेको अन्तिम तत्वमा मान बचत गर्नुहोस्। अब दायाँ देखि बाँया सुरू गर्नुहोस्, जसबाट २ बाट सुरु हुन्छnd एर्रेको अन्तिम एलिमेन्ट, अब २ को संख्या र दिईएको एर्रे एलिमेन्ट्समा संख्याको गुण प्राप्त गर्नुहोस् र यसलाई उपसर्ग एर्रेको अघिल्लो मानको साथ थप्नुहोस्। यसलाई उपसर्ग एरेको मानहरूको साथ थप्न जारी राख्नुहोस् र उपसर्ग एर्रेको सम्बन्धित ठाउँमा भण्डार गर्नुहोस्।

हामीलाई दिइएको प्रत्येक क्वेरीको लागि जाँच गर्नुहोस् कि सही मान एर्रेको अन्तिम अनुक्रमणिका बराबर छैन। यदि यो सहि पाइएको छ भने फर्क उपसर्ग एर्रे [बायाँ] र उपसर्ग एर्रे [दायाँ] पाउनुहोस् र यसलाई बनेको मानमा विभाजन गर्नुहोस् जब हामी २ को शक्तिमा सिफ्ट अपरेसन लागू गर्छौं र त्यो मान फिर्ता गर्छौं, अन्यथा केवल फर्क फिर्ता गर्नुहोस्। उपसर्ग एर्रेको [बाँया] र सहि मानमा सिफ्ट अपरेसनको साथ विभाजन गर्नुहोस् र फिर्ता गर्नुहोस्।

कार्यान्वयन

C ++ कार्यक्रम

#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

बाइनरी एर्रेको सबब्रेयसको दशमलव मानहरूको लागि प्रश्नहरूको लागि जटिलता विश्लेषण

समय जटिलता

O (q) जहाँ "क्यू" क्वेरीहरूको संख्या हो।

ठाउँ जटिलता

ऊ) जहाँ "N" एर्रेमा एलिमेन्ट्सको संख्या हो।

संदर्भ