بائنری صف کے سبریوں کی اعشاریہ اقدار کے لئے سوالات


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون گوگل
لڑی سوال کا مسئلہ

کسی بائنری صف میں بائنری صف کی سبریوں کے اعشاریہ اقدار کے ل Qu سوالات لکھیں۔ مسئلے کے بیان میں بائنری صف میں رینج کی مدد سے تشکیل دی گئی اعشاریہ نمبر تلاش کرنے کے لئے کہا گیا ہے۔

مثال کے طور پر

ان پٹ:

ارر [] = {1، 0 ، 1 ، 1 ، 0 ، 0 ، 1 ، 1}

سوال (1 ، 5)

سوال (3 ، 6)

: پیداوار

12 9

وضاحت:

بائنری نمبر کے طور پر تشکیل پائے جانے والے آؤٹ پٹ میں 1 سے 5 تکمیل (01100) کی حدود میں نمائندگی کرنے والے بائنری نمبر 12 ہیں۔

پیداوار کے طور پر تشکیل دیا بائنری نمبر 3 سے 6 تک مشتمل (1001) کی حد میں نمائندگی کرنا 9 ہے۔

بائنری صف کی سبریوں کی اعشاریہ اقدار کے لئے سوالات

 

بائنری صف کی سبریوں کی اعشاریہ اقدار کے ل Qu سوالات کے لئے الگورتھم

  1. ایک ارے کو پریفیکس آرے کے بطور بنائیں ، اسے 0 سے شروع کریں۔
  2. ماقبل کے آخری عنصر کو آخری عنصر میں کاپی کریں صف دیا
  3. سرنی کے دائیں سے بائیں سرے میں سے گزریں ، اور دیئے گئے سرنی عنصر کی مصنوع اور 2 کی طاقتوں کو اسٹور کریں اور اسے سابقہ ​​اری کے ساتھ شامل کریں۔
  4. استفسار حاصل کریں ، اگر ویلیو رائٹ دیئے گئے صف کی آخری انڈیکس ویلیو کے برابر نہیں ہے تو ، سابقہ ​​ارے [بائیں] اور سابقہ ​​ارے [دائیں + 1] کے فرق کی تقسیم اور 1 اور دائیں کے شفٹ آپریشن کو واپس کریں۔ سرنی کا اشاریہ۔
  5. بصورت دیگر ارفع کی تقسیم [دائیں] اور 1 کے شفٹ آپریشن اور سرنی کے دائیں اشاریہ کو واپس کریں۔

بائنری صف کے سبریوں کی اعشاریہ اقدار کے لئے سوالات کے لئے وضاحت

مسئلے کے بارے میں بائنری صف کی سبریوں کی اعشاریہ اقدار کے لئے سوالات ، دیئے گئے ایک بائنری سرنی اور بائیں اشاریہ اور دائیں اشاریہ کی طرح اشاریہ کی ایک حد۔ دیئے گئے حد کے ساتھ تشکیل دیئے گئے بائنری نمبر کی اعشاری شکل تلاش کریں۔ ہمیں ایک استفسار دیا جائے گا جس میں ہم نے رینج دی ہے۔ ہمیں حدود کے ساتھ بائنری نمبر کی تشکیل کردہ اعشاریہ کو تلاش کرنا ہوگا۔ اس کے ل we ، ہم سائز کی ایک اضافی صف تیار کرنے جارہے ہیں جس طرح سرنی کی لمبائی ہے۔ ہم اس صف کی تعمیر کریں گے یا ہم کہہ سکتے ہیں کہ ہم اس عمل کو پہلے سے تیار کرسکتے ہیں اور اس میں کچھ اقدار کو بھر سکتے ہیں تاکہ ہم سوال کو مستقل وقت پر حل کرسکیں۔

صف کو عبور کریں ، لیکن سرنی کو عبور کرنے سے پہلے ، صف کو 0 سے پُر کریں جب جاوا میں جب سرنی تیار ہوجائے گی تو وہ خود بخود 0 سے پُر ہوجاتی ہے ، لیکن C ++ میں ہمیں خود ہی کرنا ہے۔ اس کے بعد ، آخری صف عنصر اور 1 کی مصنوع حاصل کریں ، صیغہ آرے کے آخری عنصر میں قدر کو بچائیں۔ اب دائیں سے بائیں شروع کریں ، یعنی 2 سے شروع کریںnd سرنی کا آخری عنصر ، اب طاقتوں میں نمبروں کی پیداوار 2 اور دیئے گئے سرنی عنصر کو حاصل کریں اور اسے سابقہ ​​اری کی پچھلی قیمت کے ساتھ شامل کریں۔ اسے سابقہ ​​اری کی اقدار کے ساتھ شامل کرتے رہیں اور اسے سابقہ ​​ارای کی متعلقہ جگہ پر اسٹور کریں۔

ہمیں دیئے گئے ہر سوال کے ل check ، چیک کریں کہ کیا صحیح قیمت سرنی کے آخری انڈیکس کے برابر نہیں ہے۔ اگر یہ سچ ہے ، تو فرق کا ماہر ارے [بائیں] اور سابقہ ​​آرری [دائیں] حاصل کریں اور اس کی تشکیل کردہ قیمت کے ساتھ تقسیم کریں جب ہم 2 کے اختیارات میں شفٹ آپریشن کا اطلاق کرتے ہیں اور اس قدر کو واپس کرتے ہیں ، ورنہ محض فرق واپس کردیں۔ پریفیکس ارے [بائیں] کی اور اسے صحیح قدر پر شفٹ آپریشن کے ساتھ تقسیم کریں اور اسے لوٹائیں۔

عمل

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) کہاں "ق" سوالات کی تعداد ہے۔

خلائی پیچیدگی

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔

حوالہ