የእነሱ XOR 0 እንደሆነ በአንድ ጥምር ውስጥ ጥንድ ቁጥር ያግኙ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ ካዴንስ ህንድ ኩፖንዱኒያ Honeywell በእርግጥም InfoEdge የሞንፎርግ ቤተ ሙከራዎች Pinterest
ሰልፍ ቢት ሃሽ በመፈለግ ላይ መደርደር

ችግሩ “የእነሱ XOR 0 በሆነ መጠን ጥንድ ቁጥር በአንድ ድርድር ውስጥ ያግኙ” የሚለው ነው ፣ እኛ ሰጥተናል ደርድር of ኢንቲጀሮች. የችግሩ መግለጫ ጥንድ ባለው ድርድር ውስጥ የሚገኙትን ጥንዶች ቁጥር ለማወቅ ይጠይቃል Ai XOR Aj = 0.

ማሳሰቢያ-1 ያነሰ ወይም እኩል ነው i, i ያንሳል jj ከ 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. I <n (የዝርዝሩ ርዝመት) እያለ ድርድርን ያቋርጡ።
    1. እኛ በፈጠርነው ድርድር ውስጥ የእያንዲንደ ድርድር አባል ድግግሞሾችን ቆጥረው ያከማቹ።
  4. የቁጥር ድርድርን ያቋርጡ ፣ i <= ከፍተኛው አካል።
    1. ውፅዓት = ውፅዓት + ቆጠራ [i] * (ቆጠራ [i] - 1);
  5. የመመለስ ውጤት / 2.

ማስረጃ

ብዛት ያላቸው የቁጥር ቁጥሮች አሉን ፡፡ የችግሩ መግለጫ እንደዚህ ባሉ ድርድር ውስጥ የሚገኙትን ጥንዶች ለማወቅ ይጠይቃል Ai XOR Aj = 0. የመረጃ ጠቋሚ ካርታ እንጠቀማለን ፣ ይህም ማለት የእያንዲንደ ድርድር አባላትን ድግግሞሽ እንቆጥራቸዋለን እናም እነሱ መቁጠር ከቻሉ እነሱን ማወቅ እንችል ነበር [i] * count [i-1] ውጤት ይህንን ለመጠቀም አንድ ደርድር እና በዚያ ንጥረ ነገር ድግግሞሽ የምናከማችበት የቁጥር ድርድር መረጃ ጠቋሚ ሆኖ በሚሠራው የድርድር ክፍል ውስጥ ስለዚህ አንድ ቁጥር በአንድ የተወሰነ ቦታ ከተገኘ እንደ መረጃ ጠቋሚ እንጠቀምበታለን።

ከድርድሩ ውስጥ ከፍተኛውን ንጥረ ነገር እናገኛለን። እና ከዚያ ከፍተኛው ንጥረ ነገር መጠን አንድ ድርድር እናደርጋለን ፣ ይህ የቁጥር ድርድር ነው ፣ ይህ እንደ ድግግሞሽ ድርድር እንጠቀምበታለን። ድርድርን ማለፍ እና የእያንዲንደ ድርድር አባላትን ብዛት ማከማቸት ያስፈልገናል። ከዚያ የውጤቱን ተለዋዋጭ ወደ 0 እናዘጋጃለን።

እስቲ አንድ ምሳሌ እንመልከት-

ለምሳሌ

arr [] = {2, 3, 1, 3, 2} ከፍተኛው የድርድር መጠን 3 ይሆናል።

i = 0 ፣ arr [i] = 2 ፣ እኛ እንቆጥረዋለን [arr [i]] + = 1 ፣ ይህ ማለት የቁጥር ንጥረ ነገር 2 ኛ መረጃ ጠቋሚ በ 1 ይጨምራል ማለት ነው።

i = 1 ፣ arr [i] = 3 ፣ እኛ እንቆጥረዋለን [arr [i]] + = 1 ፣ ይህ ማለት የቁጥር ንጥረ ነገር 3 ኛ መረጃ ጠቋሚ በ 1 ይጨምራል ማለት ነው።

i = 2 ፣ arr [i] = 1 ፣ እኛ እንቆጥረዋለን [arr [i]] + = 1 ፣ ይህ ማለት የቁጥር ንጥረ ነገር 1 ኛ መረጃ ጠቋሚ በ 1 ይጨምራል ማለት ነው።

i = 3 ፣ arr [i] = 3 ፣ እኛ እንቆጥረዋለን [arr [i]] + = 1 ፣ ይህ ማለት የቁጥር ንጥረ ነገር 3 ኛ መረጃ ጠቋሚ በ 1 ይጨምራል ማለት ነው።

i = 4 ፣ arr [i] = 2 ፣ እኛ እንቆጥረዋለን [arr [i]] + = 1 ፣ ይህ ማለት የቁጥር ንጥረ ነገር 2 ኛ መረጃ ጠቋሚ በ 1 ይጨምራል ማለት ነው።

የቆጠራው ድርድር እንደ ቆጠራ አለን [] = {0,1,2,2}

ይህንን ድርድር እናቋርጣለን ፣ እና ውጤትን በምናደርግ ቁጥር ‹ውፅዓት + ቆጠራ [i] * (ቆጠራ [i] - 1) ፡፡

እናም ውጤቱን እንደ ውጤት / 2 ይመልሰዋል።

የእነሱ ጥምር XOR 0 በሆነ ድርድር ውስጥ ጥንድ ቁጥር ለማግኘት የ C ++ ኮድ

#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) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። በድርድሩ ውስጥ ያሉትን ንጥረ ነገሮች ለመድረስ ኦ (1) ጊዜ ያስፈልጋል። ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

የቦታ ውስብስብነት

ኦ (ማክስ) ፣ በሰልፍ ውስጥ ካሉ ሁሉም ንጥረ ነገሮች መካከል ማክስ ከፍተኛው ንጥረ ነገር የት ነው።