ڏنل حدن ۾ برابر يا گهٽ نمبر جي امڪان بابت سوال


تڪليف جي سطح سخت
بار بار پڇڻ ۾ گوگل Honeywell سليمان وساڻ
ڪيريو

اسان هڪ ڏني آهي صف انٽيگر ، ق سوالن جو تعداد. جتي هر سوال ۾ ٽن انٽيگرنز شامل آهن ، جيڪي هڪ قسم جي سوال جي وضاحت ڪن ٿا. انهي جو مطلب آهي ته جيڪڏهن اسان 0 ڏنو آهي انهي جو مطلب آهي اسان کي ڏنل حد ۾ بيضا نمبر چونڊڻ جو امڪان ڳولڻو آهي. جتي رينج هڪ شروعاتي پوائنٽ ۽ هڪ ختم ٿيڻ واري نقطي جي طور تي وضاحت ڪئي وئي آهي. ڪنهن خاص قسم جي ڪنهن خاص سوال جي هن وڏي حد اندر. توھان کي ھر سوال جو حل ڳولڻو پوندو. هر سوال جي شڪل ۾ هوندو

TSE: جيڪڏهن توهان T = 0 ڏنو آهي ، انهي جو مطلب آهي توهان کي ڏنل حد ۾ هڪ جيتري نمبر چونڊڻ جو امڪان ڳولڻو پوندو (ايس: شروعاتي پوائنٽ ، اي: ختم ٿيڻ واري پوائنٽ) ڏنل صف ۾ اي.

TSE: جيڪڏهن توهان T = 1 ڏنو آهي ، ته انهي جو مطلب آهي توهان کي ڏنل رينج ۾ بي جوڙ نمبر چونڊڻ جو امڪان ڳولڻو پوندو (ايس: شروعاتي پوائنٽ ، اي: ختم ٿيڻ واري پوائنٽ) ڏنل صف ۾ اي.

مثال

انٽرويو

صف [] = {2 ، 3 ، 4 ، 5 ، 6}

سوال 1: 1 1 3

سوال 1: 0 1 4

پيداوار:

1 / 3

1 / 2

وضاحت:

اسان ٽي = 1 ڏنو آهي ، هڪ پڇاڙيءَ ۾ ، مطلب ته اسان کي 1 ۽ 3 جي حد ۾ هڪ بي جوڙ نمبر چونڊڻ جو امڪان ڳولڻو آهي.

اسان T = 0 ڏنو آهي ، هڪ سوال ۾ ، معني اسان کي 1 ۽ 4 جي حد تائين به برابر نمبر چونڊڻ جو امڪان ڳولڻو آهي.

ڏنل حدن ۾ برابر يا گهٽ نمبر جي امڪان بابت سوال

الورورٿم

  1. گندي نمبرن ۽ اڃا به نمبرن لاءِ ٻه آيتون ٺاهيو ، هڪ جيتري سائيز جون ساڳيون آهن. ٻنھي جي صفن جي پھرئين عنصر کي 0 کان شروعاتي ڪريو.
  2. صف کي ڳوڙها ۽ چيڪ ڪريو ته عدد بي جوڙ آهي پوءِ عدد نمبر جي قيمت ڀريو اسان جوڙيندڙ نمبر [i] + 1 ۽ برابر جي صف ۾ اسان پيدا ڪيو جيتوڻيڪ نمبر [i] ۽ ساڳيو نمبر جيڪڏهن اسان کي ملي به وڃي ، هاڻوڪي نمبر کي موجوده گُٽ نمبر نمبر واري صف ۾ محفوظ ڪريو ، ۽ بيڊ نمبر نمبر کي بي جوڙ نمبر جوڙ.
  3. کان پڇڻ واريون ڀيرا تائين سوال ڪريو ، ۽ سا rightي ، کاٻي ۽ 1 جو فرق محفوظ ڪريو.
  4. چيڪ ڪريو ته اسان کي امڪاني ڳولڻ لاءِ به برابر نمبر يا ٻڙو نمبر چونڊڻو آهي ، جيڪڏهن هڪ گدو نمبر ، ته پوءِ قدر کي oddNumber [صحيح] ۽ odd نمبر جي فرق جي طور تي ذخيرو ڪريو [کاٻي - 1].
  5. ايلس پراباب ۾ قدر برابر نمبر (درست) ۽ اڃا نمبر نمبر جي فرق جي طور تي [بائیں - 1].
  6. پڙتال ڪريو ته اهو امڪان 0 کان گهٽ يا برابر آهي ، پوءِ پرنٽ ڪيو ـ ايلس جيڪڏهن اهو برابر آهي ته برابر آهي ، پوءِ پرنٽ 0. ايلس ڳوليندا انهن نعمتن جو ڪل تعداد جيڪو ڳڻجي سگهجي ٿو.
  7. قيمت ڀوڳ ۽ نعمتن جو تعداد ڇاپيو.

وضاحت

اسان ھڪڙي جڳھ لاءِ ٻه نمبر ٺاھڻ وارا آھن ھڪڙي ھڪڙي ۽ ذخيرو نمبر لاءِ. هاڻي ، اسان لهه کي ترتيب ڏيڻ وڃون ٿا ۽ اهو ڳوليندا ته صف جو عنصر طاق آهي يا جيڪڏهن اهو بي جوڙ آهي. اسان اڃا تائين نمبر نمبر بيڊ نمبر وارين ترتيب ڏيندي. ۽ اڃا نمبر جي موجوده قيمت تائين اڃا تائين نمبر نمبر ، ساڳئي نمبر تي هلڻو آهي جيڪڏهن نمبر برابر آهي. ان کان پوء ھڪڙي عددي نمبر کي نمبر نمبر صف ۽ بيڊ نمبر نمبر جي اڳوڻي قيمت کي موجوده نمبر نمبر جي موجوده قيمت ڏانھن. هي سڀ ترتيب سان ٺاهيل صفن ۾ نمبرن سان ترتيب ڏيڻ ۽ پيدا ڪرڻ آهي.

سوال جي قسم حاصل ڪريو ، کاٻي ۽ سا pointsي پوائنٽن کي ھڪڙي حد تائين ، انھن جو فرق حاصل ڪريو اسان ڳوليندا سين ته ڏنل قسم جو آهي. جيڪڏهن اهو 1 کان وڏو آهي ، ته اسان کي برابر نمبر چونڊڻ جو امڪان ڳولڻ لاءِ اڻ گهربل نمبر چونڊڻو پوندو. ٻي صورت ۾ اسان رينج جي اندر به نمبر جو امڪان ڳوليندا. جيڪڏهن اهو بي جوڙ آهي ، ته اسان ٺاهيل بيٺل نمبر جي صف جو فرق حاصل ڪنداسين ۽ ساڳيو نمبر امڪاني سان ، ساڳي نمبر جو فرق. اسان فرق کي ذخيرو ڪري ڇڏينداسين ، ۽ جيڪڏهن ممڪنه 0 کان گهٽ يا برابر جي هجي ، اسان 0 ڇاپينداسين ، ٻي صورت ۾ اهو ممڪن آهي ته ڪو ، پرنٽ 1 جي برابر آهي ، ٻي صورت ۾ اسان کي گهرائي جي ڀرپور تعداد ڳولڻ جي ضرورت آهي. ۽ نيٺ ، قيمتي امڪاني ۽ فائدا ڇپايو.

تي عملدرآمد

سي ++ پروگرام سوالن لاءِ امڪاني يا اي بي نمبر جي امڪانن تي ڏنل حدن ۾

#include<iostream>

using namespace std;

#define C 3

int getDivisor(int a, int b)
{
    if (a == 0 || b == 0)
        return 0;

    if (a == b)
        return a;

    if (a > b)
        return getDivisor(a - b, b);

    return getDivisor(a, b - a);
}

void solveQuery(int arr[], int n, int Q,int query[][C])
{
    int evenNumber[n + 1];
    int oddNumber[n + 1];
    evenNumber[0] = oddNumber[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] & 1)
        {
            oddNumber[i + 1] = oddNumber[i] + 1;
            evenNumber[i + 1] = evenNumber[i];
        }
        else
        {
            evenNumber[i + 1] = evenNumber[i] + 1;
            oddNumber[i + 1] = oddNumber[i];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int right = query[i][2];
        int left = query[i][1];
        int T = query[i][0];

        int dif = right - left + 1;
        int probab;

        if (T)
            probab = oddNumber[right] - oddNumber[left - 1];
        else
            probab = evenNumber[right] - evenNumber[left - 1];

        if (!probab)
            cout << "0" << endl;

        else if (probab == dif)
            cout << "1" << endl;

        else
        {
            int div = getDivisor(probab, dif);
            cout << probab / div << "/" << dif / div << endl;
        }
    }
}

int main()
{
    int arr[] = { 2,3,4,5,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2;
    int query[Q][C] = { { 1, 1, 3 },
        { 0, 1, 4 }
    };

    solveQuery(arr, n, Q, query);
    return 0;
}
1/3
1/2

جاوا پروگرام سوالن تي جاوا يا انوڊ نمبر جي امڪانن تي ڏنل حدن ۾

public class QueryProbability
{
    static int getDivisor(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return getDivisor(a - b, b);

        return getDivisor(a, b - a);
    }
    
    static void solveQuery(int []arr, int n, int Q, int [][]query)
    {
        int []evenNumber = new int[n + 1];
        int []oddNumber = new int[n + 1];
        evenNumber[0] = oddNumber[0] = 0;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) > 0)
            {
                oddNumber[i + 1] = oddNumber[i] + 1;
                evenNumber[i + 1] = evenNumber[i];
            }
            else
            {
                evenNumber[i + 1] = evenNumber[i] + 1;
                oddNumber[i + 1] = oddNumber[i];
            }
        }
        
        for (int i = 0; i < Q; i++)
        {
            int right = query[i][2];
            int left = query[i][1];
            int T = query[i][0];

            int dif = right - left + 1;
            int probab;
            if (T > 0)
                probab = oddNumber[right] - oddNumber[left - 1];
            else
                probab = evenNumber[right] - evenNumber[left - 1];

            if (probab <= 0)
                System.out.println("0");
            else if (probab == dif)
                System.out.println("1");

            else
            {
                int div = getDivisor(probab, dif);
                System.out.println(probab / div + "/" +dif / div);
            }
        }
    }
    
    static public void main (String[] args)
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        int Q = 2;
        int [][]query = { { 1, 1, 3 },
            { 0, 1, 4 }
        };

        solveQuery(arr, n, Q, query);
    }
}
1/3
1/2

ڏنل حدن ۾ برابر يا گهٽ نمبر جي امڪان تي سوالن جي پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (ق * ن) جتي "ق" سوالن جو تعداد آهي ۽ “ن” صف ۾ موجود عنصرن جو تعداد آهي

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

حوالي