એરેમાં જોડીની સંખ્યા શોધો જેમ કે તેમનો XOR 0 છે  


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે કેડન્સ ભારત કુપનદુનિયા હનીવેલ ખરેખર માહિતી એડજ મૂનફ્રોગ લેબ્સ Pinterest
અરે બિટ્સ હેશ શોધી રહ્યું છે સોર્ટિંગ

સમસ્યા "એરેમાં જોડીની સંખ્યા શોધો જેમ કે તેમનો XOR 0 છે" રાજ્ય એવું માને છે કે, આપણે એક આપ્યું છે એરે of પૂર્ણાંક. સમસ્યા નિવેદન એરેમાં જોડીની સંખ્યા શોધવા માટે પૂછે છે, જેમાં જોડી છે Ai એક્સઓઆર 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. ગણતરીના એરેને પસાર કરો, જ્યારે હું <= મહત્તમ તત્વ.
    1. આઉટપુટ = આઉટપુટ + ગણતરી કરો [i] * (ગણતરી [i] - 1);
  5. રીટર્ન આઉટપુટ / 2.

સમજૂતી

આપણી પાસે પૂર્ણાંકોની એરે છે. સમસ્યાનું નિવેદન એરેમાં હાજર જોડી શોધવા માટે પૂછે છે Ai એક્સઓઆર Aj = 0. અમે અનુક્રમણિકા મેપિંગનો ઉપયોગ કરવા જઈ રહ્યા છીએ, જેનો અર્થ છે કે આપણે દરેક એરે એલિમેન્ટની આવર્તનની ગણતરી કરીશું જેમ કે તેઓ ગણતરી કરી શકે તો અમે તેમને શોધી શકીએ [i] * ગણતરી [i-1] અને પરિણામે આઉટપુટ. આનો ઉકેલ લાવવા માટે એરે અને એરે એલિમેન્ટની તે જગ્યાએ જે ગણતરીના એરેના અનુક્રમણિકા તરીકે કાર્ય કરે છે જેમાં આપણે આપણા તત્વોની આવર્તન સંગ્રહવા જઈએ છીએ, તેથી જો કોઈ સંખ્યા કોઈ ચોક્કસ સ્થળે મળી આવે, તો અમે તેનો ઉપયોગ અનુક્રમણિકા તરીકે કરીશું.

આ પણ જુઓ
બાઈનરી એરે પર ક્વેરીઝ ગણતરી અને ટogગલ કરો

અમને એરેમાંથી મહત્તમ તત્વ મળશે. અને તે મહત્તમ તત્વ કદમાંથી, આપણે એક એરે બનાવીશું, આ ગણતરી એરે છે, આ આપણે ફ્રીક્વન્સી એરે તરીકે વાપરવા જઈશું. આપણે એરેને પસાર કરવાની અને દરેક એરે એલિમેન્ટની ગણતરી સ્ટોર કરવાની જરૂર છે. પછી આપણે આઉટપુટ વેરીએબલ 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 લી અનુક્રમણિકા 1 દ્વારા વધશે.

i = 3, એરે [i] = 3, અમે ગણતરી કરીશું [એઆરઆર [i]] + = 1, તેનો અર્થ છે કે ગણતરીના તત્વનો ત્રીજો અનુક્રમણિકા 3 દ્વારા વધશે.

i = 4, એરે [i] = 2, અમે ગણતરી કરીશું [એઆરઆર [i]] + = 1, તેનો અર્થ છે કે ગણતરીના તત્વનો બીજો અનુક્રમણિકા 2 દ્વારા વધશે.

આપણી પાસે ગણતરીની ગણતરીની એરે છે [] = {0,1,2,2}

અમે આ એરેને પસાર કરીશું, અને દરેક વખતે જ્યારે આઉટપુટ = આઉટપુટ + ગણતરી કરીએ [i] * (ગણતરી [i] - 1).

અને તે આઉટપુટ / 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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. એરેમાંના તત્વોને forક્સેસ કરવા માટે ઓ (1) સમય આવશ્યક છે. આમ સમય જટિલતા રેખીય છે.

આ પણ જુઓ
સortedર્ટ કરેલા રોટેટેડ એરેમાં એક એલિમેન્ટ શોધો

અવકાશ જટિલતા

ઓ (મેક્સ), જ્યાં મેરે એરેના બધા તત્વોમાં મહત્તમ તત્વ છે.