ഒരു അറേയിലെ ജോഡികളുടെ എണ്ണം കണ്ടെത്തുക, അവയുടെ XOR 0


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു കഡെൻസ് ഇന്ത്യ കൂപ്പൺ‌ഡ്യൂണിയ ഹണിവെൽ തീർച്ചയായും വിവരം മൂൺഫ്രോഗ് ലാബുകൾ പോസ്റ്റ്
അറേ ബിറ്റുകൾ ഹാഷ് തിരയുന്നു ക്രമപ്പെടുത്തൽ

“ഒരു അറേയിലെ ജോഡികളുടെ എണ്ണം കണ്ടെത്തുക, അതായത് അവരുടെ XOR 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. ഞാൻ <n (അറേയുടെ നീളം) ആയിരിക്കുമ്പോൾ അറേയിലൂടെ സഞ്ചരിക്കുക.
    1. ഞങ്ങൾ സൃഷ്ടിച്ച അറേയിലെ ഓരോ അറേ ഘടകത്തിന്റെയും ആവൃത്തികൾ കണക്കാക്കി സംഭരിക്കുക.
  4. ഞാൻ <= പരമാവധി ഘടകം ആയിരിക്കുമ്പോൾ എണ്ണം അറേയിലൂടെ സഞ്ചരിക്കുക.
    1. Output ട്ട്‌പുട്ട് ചെയ്യുക = + ട്ട്‌പുട്ട് + എണ്ണം [i] * (എണ്ണം [i] - 1);
  5. Output ട്ട്‌പുട്ട് / 2 നൽകുക.

വിശദീകരണം

ഞങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിരയുണ്ട്. ഒരു അറേയിൽ നിലവിലുള്ള ജോഡി കണ്ടെത്താൻ പ്രശ്‌ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു Ai XOR Aj = 0. ഞങ്ങൾ ഇൻഡെക്സ് മാപ്പിംഗ് ഉപയോഗിക്കാൻ പോകുന്നു, അതിനർത്ഥം ഓരോ അറേ ഘടകത്തിന്റെയും ആവൃത്തി ഞങ്ങൾ കണക്കാക്കാൻ പോകുന്നു, അതായത് അവയ്ക്ക് [i] * എണ്ണം [i-1] എണ്ണാൻ കഴിയുമെങ്കിൽ അവ കണ്ടെത്താനാകും. .ട്ട്‌പുട്ട്. ഇത് പരിഹരിക്കാൻ ഒരു ശ്രേണി ഞങ്ങളുടെ ഘടകങ്ങളുടെ ആവൃത്തി സംഭരിക്കാൻ പോകുന്ന എണ്ണം അറേയുടെ സൂചികയായി പ്രവർത്തിക്കുന്ന അറേ എലമെന്റിന്റെ സ്ഥലത്ത്, അതിനാൽ ഒരു പ്രത്യേക സ്ഥലത്ത് ഒരു നമ്പർ കണ്ടെത്തിയാൽ, ഞങ്ങൾ അത് ഒരു സൂചികയായി ഉപയോഗിക്കാൻ പോകുന്നു.

അറേയിൽ നിന്നുള്ള പരമാവധി ഘടകം ഞങ്ങൾ കണ്ടെത്തും. ആ പരമാവധി മൂലക വലുപ്പത്തിൽ, ഞങ്ങൾ ഒരു അറേ നിർമ്മിക്കാൻ പോകുന്നു, ഇതാണ് ക count ണ്ട് അറേ, ഇത് ഞങ്ങൾ ഒരു ഫ്രീക്വൻസി അറേ ആയി ഉപയോഗിക്കാൻ പോകുന്നു. നമുക്ക് അറേയിലൂടെ സഞ്ചരിച്ച് ഓരോ അറേ ഘടകത്തിന്റെയും എണ്ണം സംഭരിക്കേണ്ടതുണ്ട്. അപ്പോൾ നമ്മൾ variable ട്ട്‌പുട്ട് വേരിയബിൾ 0 ആയി സജ്ജമാക്കും.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

arr [] = {2, 3, 1, 3, 2} അറേയുടെ പരമാവധി വലുപ്പം 3 ആയിരിക്കും.

i = 0, arr [i] = 2, ഞങ്ങൾ എണ്ണം [arr [i]] + = 1 ചെയ്യും, അതിനർത്ഥം എണ്ണത്തിന്റെ മൂലകത്തിന്റെ രണ്ടാമത്തെ സൂചിക 2 വർദ്ധിപ്പിക്കും.

i = 1, arr [i] = 3, ഞങ്ങൾ എണ്ണം [arr [i]] + = 1 ചെയ്യും, അതിനർത്ഥം എണ്ണത്തിന്റെ മൂലകത്തിന്റെ രണ്ടാമത്തെ സൂചിക 3 വർദ്ധിപ്പിക്കും.

i = 2, arr [i] = 1, ഞങ്ങൾ എണ്ണം [arr [i]] + = 1 ചെയ്യും, അതിനർത്ഥം എണ്ണത്തിന്റെ മൂലകത്തിന്റെ ആദ്യ സൂചിക 1 വർദ്ധിപ്പിക്കും.

i = 3, arr [i] = 3, ഞങ്ങൾ എണ്ണം [arr [i]] + = 1 ചെയ്യും, അതിനർത്ഥം എണ്ണത്തിന്റെ മൂലകത്തിന്റെ 3 മത്തെ സൂചിക 1 വർദ്ധിപ്പിക്കും.

i = 4, arr [i] = 2, ഞങ്ങൾ എണ്ണം [arr [i]] + = 1 ചെയ്യും, അതിനർത്ഥം എണ്ണത്തിന്റെ മൂലകത്തിന്റെ രണ്ടാമത്തെ സൂചിക 2 വർദ്ധിപ്പിക്കും.

ഞങ്ങൾക്ക് എണ്ണത്തിന്റെ അറേ എണ്ണം [] = {0,1,2,2}

ഞങ്ങൾ ഈ ശ്രേണിയിലൂടെ സഞ്ചരിക്കും, ഓരോ തവണ output ട്ട്‌പുട്ട് = + ട്ട്‌പുട്ട് + എണ്ണം [i] * (എണ്ണം [i] - 1).

അത് output ട്ട്‌പുട്ട് / ട്ട്‌പുട്ട് / 2 ആയി നൽകും.

ഒരു അറേയിലെ ജോഡികളുടെ എണ്ണം കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്, അതായത് അവരുടെ XOR 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. അറേയിലെ ഘടകങ്ങൾ ആക്‌സസ് ചെയ്യുന്നതിന് O (1) സമയം ആവശ്യമാണ്. അങ്ങനെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

ഓ (പരമാവധി), ഇവിടെ അറേയിലെ എല്ലാ ഘടകങ്ങളിലും പരമാവധി ഘടകമാണ് മാക്സ്.