একটি অ্যারেতে জোড়াগুলির সন্ধান করুন যেমন তাদের এক্সওআর 0 হয়  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় ক্যাডেন্স ইন্ডিয়া কুপনডুনিয়া Honeywell প্রকৃতপক্ষে তথ্যপ্রযুক্তি মুনফ্রোগ ল্যাব পিন্টারেস্ট
বিন্যাস বিটস কাটা খোঁজ শ্রেণীবিভাজন

সমস্যাটি "একটি অ্যারেতে জোড়াগুলির সন্ধান করুন যেমন তাদের এক্সওআর 0 হয়" রাষ্ট্রটি অনুমান করে যে, আমরা একটি দিয়েছি বিন্যাস of পূর্ণসংখ্যার। সমস্যা বিবৃতিটি একটি অ্যারেতে উপস্থিত জোড়গুলির সংখ্যা জানতে জিজ্ঞাসা করে, যার জুড়ি রয়েছে Ai XOR যাও Aj = 0

দ্রষ্টব্য: 1 এর চেয়ে কম বা সমান i, i কম j এবং j n (1 <=) এর চেয়ে কম বা সমানi < j<= n)।

উদাহরণ  

একটি অ্যারেতে জোড়াগুলির সন্ধান করুন যেমন তাদের এক্সওআর 0 হয়

arr[] = {2, 3, 1, 3, 2}
2

ব্যাখ্যা

সূচক (0,4) এবং (1,3)।

arr[] = {1, 1, 1}
3

অ্যালগরিদম  

  1. একটি অ্যারে উপস্থিত সর্বাধিক উপাদানটি সন্ধান করুন।
  2. আকারের একটি অ্যারে তৈরি করুন (সর্বাধিক উপাদান)।
  3. আমি <এন (অ্যারের দৈর্ঘ্য) এর সাথে অ্যারেটি অতিক্রম করুন।
    1. আমরা তৈরি অ্যারেতে প্রতিটি অ্যারের উপাদানটির ফ্রিকোয়েন্সি গণনা করুন এবং সংরক্ষণ করুন।
  4. I <= সর্বাধিক উপাদান থাকা অবস্থায় গণনার অ্যারেটি অতিক্রম করুন।
    1. আউটপুট = আউটপুট + গণনা করুন [i] * (গণনা [i] - 1);
  5. রিটার্ন আউটপুট / 2।

ব্যাখ্যা

আমরা পূর্ণসংখ্যার একটি অ্যারে আছে। সমস্যা বিবৃতিতে এমন অ্যারে উপস্থিত থাকা জুটিটি খুঁজে বের করতে বলে Ai XOR যাও Aj = 0. আমরা সূচি ম্যাপিং ব্যবহার করতে যাচ্ছি যার অর্থ আমরা প্রতিটি অ্যারের উপাদানটির ফ্রিকোয়েন্সি গণনা করতে যাচ্ছি যাতে তারা গণনা করতে পারলে আমরা তাদের বের করতে পারি [i] * গণনা [i-1] এবং ফলস্বরূপ আউটপুট এটি সমাধান করার জন্য একটি বিন্যাস এবং অ্যারের উপাদানটির সেই স্থানে যা গণনা অ্যারের সূচক হিসাবে কাজ করে যেখানে আমরা আমাদের উপাদানগুলির ফ্রিকোয়েন্সি সঞ্চয় করতে চলেছি, সুতরাং যদি কোনও নির্দিষ্ট স্থানে একটি সংখ্যা পাওয়া যায়, আমরা এটি সূচক হিসাবে ব্যবহার করতে যাচ্ছি।

আরো দেখুন
বাইনারি অ্যারেতে প্রশ্নগুলি টগল করুন এবং টগল করুন

আমরা অ্যারে থেকে সর্বাধিক উপাদানটি খুঁজে পাব। এবং যে সর্বোচ্চ উপাদান আকার, আমরা একটি অ্যারে করতে যাচ্ছি, এটি গণনা অ্যারে, এটি আমরা ফ্রিকোয়েন্সি অ্যারে হিসাবে ব্যবহার করতে যাচ্ছি। আমাদের অ্যারেটি অতিক্রম করতে হবে এবং প্রতিটি অ্যারের উপাদানগুলির গণনা সঞ্চয় করতে হবে। তারপরে আমরা আউটপুট ভেরিয়েবল 0 তে সেট করব।

আসুন একটি উদাহরণ বিবেচনা করুন:

উদাহরণ

অ্যারে [] = {2, 3, 1, 3, 2 ray অ্যারের সর্বাধিক আকার 3 হবে।

i = 0, আরআর [i] = 2, আমরা গণনা করব [আরআর [i]] + = 1, এর অর্থ গণনার উপাদানগুলির 2 র্থ সূচকটি 1 দ্বারা বৃদ্ধি পাবে।

i = 1, আরআর [i] = 3, আমরা গণনা করব [আরআর [i]] + = 1, এর অর্থ গণনার উপাদানগুলির 3 র্থ সূচকটি 1 দ্বারা বৃদ্ধি পাবে।

i = 2, আরআর [i] = 1, আমরা গণনা করব [আরআর [i]] + = 1, এর অর্থ হ'ল কাউন্টের উপাদানগুলির 1 ম সূচক 1 দ্বারা বৃদ্ধি পাবে।

i = 3, আরআর [i] = 3, আমরা গণনা করব [আরআর [i]] + = 1, এর অর্থ গণনার উপাদানগুলির তৃতীয় সূচক 3 দ্বারা বৃদ্ধি পাবে।

i = 4, আরআর [i] = 2, আমরা গণনা করব [আরআর [i]] + = 1, এর অর্থ গণনার উপাদানগুলির 2 র্থ সূচকটি 1 দ্বারা বৃদ্ধি পাবে।

আমাদের গণনা হিসাবে অ্যারে রয়েছে [] = {0,1,2,2}

আমরা এই অ্যারেটি অতিক্রম করব এবং প্রতিবার আউটপুট = আউটপুট + গণনা করব [i] * (গণনা [i] - 1)।

এবং এটি আউটপুট / 2 হিসাবে আউটপুট ফেরত দেবে।

একটি অ্যারেতে জোড়া সংখ্যা খুঁজতে সি ++ কোড যেমন তাদের এক্সওআর 0 হয়  

#include<iostream>
#include<algorithm>

using namespace std;

int calculate(int a[], int n)
{
    int *maxm = max_element(a, a + 5);
    int count[*maxm + 1] = {0};

    for(int i = 0; i < n; i++)
    {
        count[a[i]] += 1;
    }
    int output = 0;
    for(int i = 0; i < (*maxm)+1; i++)
    {
        output = output + count[i] * (count[i] - 1) ;
    }
    return output/2;
}
int main()
{
    int a[] = {2, 3, 1, 3, 2};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"XOR Pairs are : "<< (calculate(a,n));
    return 0;
}
XOR Pairs are : 2

অ্যারেতে জোড়ের সংখ্যা খুঁজতে জাভা কোডটি তাদের এক্সওআর 0 হয় XNUMX  

import java.util.Arrays;

class XORPair
{
    public static int calculate(int arr[], int n)
    {
        int max= Arrays.stream(arr).max().getAsInt();

        int count[] = new int[max+ 1];

        for (int i = 0; i < n; i++)
        {
            count[arr[i]] += 1;
        }
        int output = 0;
        for (int i = 0; i < (max) + 1; i++)
        {
            output = output + count[i] * (count[i] - 1);
        }
        return output / 2;
    }
    public static void main(String[] args)
    {
        int a[] = {2, 3, 1, 3, 2};
        int n = a.length;
        System.out.println("XOR Pairs are : "+calculate(a, n));
    }
}
XOR Pairs are : 2

জটিলতা বিশ্লেষণ  

সময় জটিলতা

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। অ্যারের উপাদানগুলিতে অ্যাক্সেসের জন্য ও (1) সময়ের প্রয়োজন। সুতরাং সময় জটিলতা রৈখিক হয়।

আরো দেখুন
সাজানো ঘোরানো অ্যারেতে একটি উপাদান অনুসন্ধান করুন

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

ও (সর্বোচ্চ), যেখানে অ্যারেতে সমস্ত উপাদানগুলির মধ্যে সর্বাধিক উপাদান।