ھڪڙي جڳھ ۾ جوڙو ڳولھيو ته انھن جو XOR 0 آھي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ سيڊنس انڊيا ڪوپن ڊنيا Honeywell يقينا Eاڻ ڏيو مونفيرف ليبز Pinterest
ڪيريو بٽس هاش ڳولها ترتيب ڏيڻ

مسئلو ”صف ۾ جوڙا جو تعداد ڳوليو ته انهن جو XOR 0 آهي” بيان ڪيو ته فرض ڪيو ، اسان هڪ ڏنو آهي صف of جيتريون. مسئلو بيان ڪيو ويو آهي صفن ۾ موجود جوڙا جو تعداد ڳولڻ جو ، جيڪو جوڙو آهي Ai XOR Aj = 0.

نوٽ: 1 کان گهٽ يا برابر آهي i, i کان گهٽ آهي j ۽ j کان گهٽ يا برابر جي اين (1 <= =i < j<= اين).

مثال

ھڪڙي جڳھ ۾ جوڙو ڳولھيو ته انھن جو XOR 0 آھي

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

وضاحت

انڊيڪس (0,4،1,3) ۽ (XNUMX،XNUMX).

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

الورورٿم

  1. صف ۾ موجود وڌ کان وڌ عنصر ڳوليو.
  2. سائيز جو هڪ مجموعو ٺاهيو (وڌ ۾ وڌ عنصر).
  3. ترتيب جي آرائش ڪريو ، جڏهن مان <آر (قطار جي ڊيگهه).
    1. اسان ٺاهيل صف ۾ هر صف واري عنصر جي تعدد کي ڳڻيو ۽ ذخيرو ڪريو.
  4. ڳڻپ واري آرڊر کي پار ڪريو ، جڏهن ته مان <= وڌ ۾ وڌ عنصر.
    1. Do output = output + count [i] * (شمار ​​[i] - 1) ؛
  5. ٻاھر ٻاھر / 2

وضاحت

اسان وٽ جوڙيرن جو هڪ سلسلو آهي. مسئلو بيان ڪيو ويو آهي جوڑوں کي ڳولڻ جي لاءِ صف ۾ جيئن ته Ai XOR Aj = 0. اسان انڊيڪس ميپنگ کي استعمال ڪرڻ وارا آهيون ، انهي جو مطلب آهي ته اسان هر ايري عنصر جي فريڪوئنسي کي ڳڻپ ڪرڻ وارا آهيون ته جيئن اسان انهن کي canاڻون ته اهي ڳڻپ ڪري سگهنٿا [i] * ڳڻپ [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 پاران وڌي ويندو.

= = 2 ، arr [i] = 1 ، اسان ڳڻپ ڪنداسين [arr [i]] + = 1 ، ان جو مطلب آهي ڳڻپ جي عنصر جو 1 انڊيڪس 1 پاران وڌي ويندو.

= = 3 ، arr [i] = 3 ، اسان ڳڻپ ڪنداسين [arr [i]] + = 1 ، ان جو مطلب آهي ڳڻپ جي عنصر جو ٽيون انڊيڪس 3 پاران وڌي ويندو.

i = 4 ، arr [i] = 2 ، اسان ڳڻپ ڪنداسين [arr [i]] + = 1 ، ان جو مطلب آهي ڳڻپ جي عنصر جو 2 انڊيڪس 1 پاران وڌي ويندو.

اسان وٽ ڳڻپ جو ارادو آهي جئين ڳڻپ [] = {0,1,2,2،XNUMX،XNUMX،XNUMX}

اسان هن لڪيل کي ڳوليندا ، ۽ هر وقت جڏهن اسان محصول = ٻاھر ڪ outputو + ڳڻپ [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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. O (1) صف ۾ عناصر تائين رسائي لاءِ وقت گهربل آهي. ان ڪري وقت جي پيچيدگي سڌي آهي.

خلائي پيچيدگي

اي (وڌ) ، جتي صف ۾ سڀني عنصرن جي وچ ۾ وڌ کان وڌ عنصر آهي.