প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজোড় সংখ্যার সম্ভাবনা সম্পর্কিত প্রশ্নগুলি


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় গুগল Honeywell উবার
বিন্যাস

আমরা একটি দিয়েছি বিন্যাস পূর্ণসংখ্যার, কিউয়ের সংখ্যা সংখ্যা। যেখানে প্রতিটি ক্যোয়ারীতে তিনটি পূর্ণসংখ্যা থাকে, যা কোয়েরির এক ধরণের সংজ্ঞা দেয়। এর অর্থ যদি আমরা 0 দিয়ে থাকে তবে এর অর্থ আমরা প্রদত্ত পরিসরে একটি বিজোড় সংখ্যা বেছে নেওয়ার সম্ভাবনাটি খুঁজে বের করতে হবে। যেখানে ব্যাপ্তিটি একটি প্রারম্ভিক বিন্দু এবং শেষের স্থান হিসাবে সংজ্ঞায়িত করা হয়। যে কোনও ধরণের নির্দিষ্ট ক্যোয়ারির এই নির্দিষ্ট পরিসরের মধ্যে। প্রতিটি প্রশ্নের জন্য আপনাকে সমাধানটি সন্ধান করতে হবে। প্রতিটি ক্যোয়ারী আকারে হবে

টিএসই: আপনি যদি টি = 0 দিয়ে থাকেন তবে এর অর্থ হ'ল প্রদত্ত অ্যারে এ-তে প্রদত্ত পরিসর (এস: শুরুর পয়েন্ট, ই: সমাপ্তি পয়েন্ট) এর একটি এমনকি সংখ্যার পছন্দ করার সম্ভাবনাটি খুঁজে পেতে হবে means

টিএসই: আপনি যদি টি = 1 দিয়ে থাকেন তবে তার অর্থ হল প্রদত্ত অ্যারে এ তে প্রদত্ত পরিসরে (এস: শুরুর পয়েন্ট, ই: সমাপ্তি পয়েন্ট) কোনও বিজোড় সংখ্যা বেছে নেওয়ার সম্ভাবনাটি আপনাকে খুঁজে পেতে হবে means

উদাহরণ

ইনপুট:

অ্যারে [] = {2, 3, 4, 5, 6}

প্রশ্ন 1: 1 1 3

প্রশ্ন 1: 0 1 4

আউটপুট:

1 / 3

1 / 2

ব্যাখ্যা:

আমরা একটি ক্যোয়ারিতে টি = 1 দিয়েছি, এর অর্থ হল আমাদের 1 এবং 3 ব্যাপ্তির মধ্যে একটি বিজোড় সংখ্যা বেছে নেওয়ার সম্ভাবনাটি খুঁজে বের করতে হবে।

আমরা একটি ক্যোয়ারিতে টি = 0 দিয়েছি, এর অর্থ হল 1 এবং 4 এর পরিসীমাতে একটি সমান সংখ্যা বেছে নেওয়ার সম্ভাবনাটি আমাদের খুঁজে বের করতে হবে।

প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজোড় সংখ্যার সম্ভাবনা সম্পর্কিত প্রশ্নগুলি

অ্যালগরিদম

  1. বিজোড় সংখ্যা এবং এমনকি সংখ্যার জন্য দুটি অ্যারে তৈরি করুন, প্রদত্ত অ্যারে হিসাবে একই আকারের। অ্যারের উভয়ের প্রথম উপাদানটি 0 এ শুরু করুন।
  2. অ্যারেটি অতিক্রম করুন এবং পরীক্ষা করে দেখুন যে সংখ্যাটি বিজোড় হয় তবে বিজোড় সংখ্যাটি তৈরি করেছি বিজোড় সংখ্যাটির অ্যারের মান পূরণ করুন [i] + 1 এবং এমনকি এমন অ্যারেতেও আমরা সংখ্যায় তৈরি করেছি [i] এবং এমনকি যদি সংখ্যাটি পাওয়া যায় তবেও বিজোড় সংখ্যাটি বর্তমান বিজোড় সমান নম্বর অ্যারে এবং বিজোড় নাম্বার অ্যারে বিজোড় সংখ্যাটি অ্যারে সঞ্চয় করুন।
  3. ক্যোয়ারীর সংখ্যার বার পর্যন্ত ট্র্যাভার্স করুন এবং ডান, বাম এবং 1 এর পার্থক্য সংরক্ষণ করুন।
  4. সম্ভাবনাটি খুঁজতে যদি আমাদের এমনকি সংখ্যা বা বিজোড় সংখ্যা বাছাই করতে হয় তা পরীক্ষা করে দেখুন, যদি কোনও বিজোড় সংখ্যা হয়, তবে পরীক্ষার মানটি বিজোড় সংখ্যা [ডান] এবং বিজোড় সংখ্যা [বাম - 1] এর পার্থক্য হিসাবে সংরক্ষণ করুন।
  5. অন্যথায় এমনকি সংখ্যার [ডান] এবং এমনকি নাম্বার [বাম - 1] এর পার্থক্য হিসাবে প্রোবটিতে মান সংরক্ষণ করুন।
  6. পরীক্ষাগুলি 0 এর চেয়ে কম বা সমান কিনা তা পরীক্ষা করুন, তারপরে 0 মুদ্রণ করুন অন্যথায় যদি এটি টেম্পের সমান হয় তবে 1 টি মুদ্রণ করুন অন্যথায় গণনা করা যায় এমন মোট অনুকূলের সংখ্যাটি সন্ধান করুন।
  7. মান প্রোব এবং আনুষঙ্গিক সংখ্যা মুদ্রণ করুন।

ব্যাখ্যা

আমরা দুটি অ্যারে তৈরি করতে যাচ্ছি একটি বিজোড় সংখ্যার জন্য এবং একটি এমনকি সংখ্যার জন্য সঞ্চয় করতে। এখন, আমরা অ্যারেটিকে অবিচ্ছিন্ন করতে যাচ্ছি এবং অ্যারের উপাদানটি বিজোড় বা এটি বিজোড় হলেও তা সন্ধান করব। আমরা বিজোড় সংখ্যাটি অ্যারেতে সমান সংখ্যাটি সংরক্ষণ করব। এবং এমনকি সংখ্যার আগের মানের পূর্বের মানটিও, সংখ্যাটি সমান হলে একই অনুসরণ করতে হবে। তারপরে বিজোড় মান এমনকি সংখ্যা নম্বর এবং অ্যারেড নাম্বার অ্যারের পূর্ববর্তী মানকে বর্তমানের বিজোড় সংখ্যাটির বর্তমান মান হিসাবে সঞ্চয় করুন। এই সমস্ত হ'ল যথাক্রমে তৈরি অ্যারেগুলিতে একটি অ্যারে তৈরি করা এবং পূরণ করা।

ক্যোয়ারির ধরণ, বাম এবং ডান পয়েন্টগুলি পরিসীমা হিসাবে আনুন, এর পার্থক্য পান। আমরা প্রদত্ত কোয়েরিটি কোন প্রকারের তা আবিষ্কার করব। যদি এটি 1 এর চেয়ে বেশি হয় তবে একটি সমান সংখ্যা বাছাইয়ের সম্ভাবনা খুঁজে বের করতে আমাদের একটি বিজোড় সংখ্যা নির্বাচন করতে হবে। অন্যথায় আমরা একটি ব্যাপ্তির মধ্যে এমনকি সংখ্যার সম্ভাবনা খুঁজে পাব। যদি এটি বিজোড় হয়, তবে আমরা বিজয় সংখ্যাটি অ্যারের পার্থক্যটি পেয়েছি এবং এটির সংখ্যার সম্ভাবনা, এমনকি সংখ্যার পার্থক্যের সাথে একই। আমরা প্রোবের মধ্যে পার্থক্যটি সংরক্ষণ করব, এবং যদি প্রোবাবটি কম বা তার সমান 0 হয়, আমরা 0 টি প্রিন্ট করব, অন্যথায় যদি এটি প্রোব কে, সমান হয় তবে 1 টি প্রিন্ট করুন se অন্যথায় আমাদের মোট পক্ষে সংখ্যা খুঁজে বের করতে হবে। এবং পরিশেষে, মান প্রোব এবং পক্ষে মুদ্রণ করুন।

বাস্তবায়ন

প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজড়িত সংখ্যার সম্ভাব্যতা সম্পর্কিত প্রশ্নের জন্য সি ++ প্রোগ্রাম

#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

প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজোড় সংখ্যার সম্ভাব্যতা সম্পর্কিত প্রশ্নের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

O (q * n) কোথায় "Q" এর প্রশ্নের সংখ্যা এবং "এন" অ্যারেতে উপাদানগুলির সংখ্যা

স্পেস জটিলতা ity

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

উল্লেখ