ਐਰੇ ਵਿੱਚ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਲੱਭੋ ਜਿਵੇਂ ਕਿ ਉਹਨਾਂ ਦਾ XOR 0 ਹੋਵੇ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੈਡੈਂਸ ਇੰਡੀਆ ਕੂਪਨਡਨੀਆ ਹਨੀਵੈੱਲ ਅਸਲ ਵਿੱਚ ਜਾਣਕਾਰੀ ਮੂਨਫ੍ਰਾਗ ਲੈਬਜ਼ ਕਿਰਾਏ ਨਿਰਦੇਸ਼ਿਕਾ
ਅਰੇ ਬਿੱਟ ਹੈਸ਼ ਖੋਜ ਕਰਨਾ ਲੜੀਬੱਧ

ਸਮੱਸਿਆ "ਐਰੇ ਵਿੱਚ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਲੱਭੋ ਜਿਵੇਂ ਕਿ ਉਹਨਾਂ ਦਾ ਐਕਸਓਆਰ 0 ਹੈ" ਉਹ ਅਵਸਥਾ ਜਿਹੜੀ ਮੰਨ ਲਵੇ, ਅਸੀਂ ਇੱਕ ਦਿੱਤਾ ਹੈ ਐਰੇ of ਪੂਰਨ ਅੰਕ. ਸਮੱਸਿਆ ਬਿਆਨ ਇਕ ਐਰੇ ਵਿਚ ਮੌਜੂਦ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕਹਿੰਦਾ ਹੈ, ਜਿਸ ਵਿਚ ਜੋੜਾ ਹੁੰਦਾ ਹੈ Ai XOR Aj = 0.

ਨੋਟ: 1 ਇਸ ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਹੈ i, i ਇਸ ਤੋਂ ਘੱਟ ਹੈ j ਅਤੇ j n (1 <=) ਤੋਂ ਘੱਟ ਜਾਂ ਇਸਦੇ ਬਰਾਬਰ ਹੈi < j<= n).

ਉਦਾਹਰਨ

ਐਰੇ ਵਿੱਚ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਲੱਭੋ ਜਿਵੇਂ ਕਿ ਉਹਨਾਂ ਦਾ XOR 0 ਹੋਵੇ

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

ਕਥਾ

ਇੰਡੈਕਸ (0,4) ਅਤੇ (1,3).

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

ਐਲਗੋਰਿਥਮ

  1. ਇੱਕ ਐਰੇ ਵਿੱਚ ਮੌਜੂਦ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਲੱਭੋ.
  2. ਅਕਾਰ ਦੀ ਇੱਕ ਐਰੇ (ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ) ਬਣਾਓ.
  3. ਐਰੇ ਨੂੰ ਪਾਰ ਕਰੋ, ਜਦੋਂ ਕਿ ਮੈਂ <ਐਨ (ਐਰੇ ਦੀ ਲੰਬਾਈ).
    1. ਸਾਡੇ ਦੁਆਰਾ ਬਣਾਈ ਗਈ ਐਰੇ ਵਿੱਚ ਹਰ ਐਰੇ ਐਲੀਮੈਂਟ ਦੀ ਬਾਰੰਬਾਰਤਾ ਨੂੰ ਗਿਣੋ ਅਤੇ ਸਟੋਰ ਕਰੋ.
  4. ਕਾ arਂਟ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰੋ, ਜਦੋਂ ਕਿ 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 ਨਾਲ ਵਧੇਗਾ.

i = 1, ਅਰਰ [i] = 3, ਅਸੀਂ ਗਿਣਤੀ ਕਰਾਂਗੇ [ਅਰਿ [i]] + = 1, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਗਿਣਤੀ ਦੇ ਤੱਤ ਦਾ ਦੂਜਾ ਸੂਚਕਾਂਕ 3 ਨਾਲ ਵਧੇਗਾ.

i = 2, ਅਰਰ [i] = 1, ਅਸੀਂ ਗਿਣਤੀ ਕਰਾਂਗੇ [ਅਰਿ [i]] + = 1, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਗਿਣਤੀ ਦੇ ਤੱਤ ਦਾ ਪਹਿਲਾ ਸੂਚਕਾਂਕ 1 ਨਾਲ ਵਧੇਗਾ.

i = 3, ਅਰਰ [i] = 3, ਅਸੀਂ ਗਿਣਤੀ ਕਰਾਂਗੇ [ਅਰਿ [i]] + = 1, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਗਿਣਤੀ ਦੇ ਤੱਤ ਦਾ ਤੀਜਾ ਤਤਕਰਾ 3 ਨਾਲ ਵਧੇਗਾ.

i = 4, ਅਰਰ [i] = 2, ਅਸੀਂ ਗਿਣਤੀ ਕਰਾਂਗੇ [ਅਰਿ [i]] + = 1, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਗਿਣਤੀ ਦੇ ਤੱਤ ਦਾ ਦੂਜਾ ਸੂਚਕਾਂਕ 2 ਨਾਲ ਵਧੇਗਾ.

ਸਾਡੇ ਕੋਲ ਗਿਣਤੀ ਦੇ ਤੌਰ ਤੇ ਕਾਉਂਟੀ ਦਾ ਐਰੇ ਹੈ [] = {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

ਐਰੇ ਵਿੱਚ ਜੋੜਿਆਂ ਦੀ ਗਿਣਤੀ ਕਰਨ ਲਈ ਜਾਵਾ ਕੋਡ ਜਿਵੇਂ ਕਿ ਉਹਨਾਂ ਦਾ XOR 0 ਹੈ

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਐਰੇ ਵਿਚਲੇ ਤੱਤ ਨੂੰ ਐਕਸੈਸ ਕਰਨ ਲਈ O (1) ਸਮਾਂ ਚਾਹੀਦਾ ਹੈ. ਇਸ ਪ੍ਰਕਾਰ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਰੇਖੀ ਹੁੰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਮੈਕਸ), ਜਿੱਥੇ ਐਰੇ ਵਿਚਲੇ ਸਾਰੇ ਤੱਤਾਂ ਵਿਚੋਂ ਅਧਿਕਤਮ ਤੱਤ ਹੁੰਦਾ ਹੈ.