រកចំនួនគូក្នុងអារេដូចជា XOR របស់ពួកគេគឺ ០


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Cadence ឥណ្ឌា CouponDunia Honeywell ជា​ការ​ពិត InfoEdge មន្ទីរពិសោធន៍ Moonfrog Pinterest
អារេ ប៊ីត ហាស់ ការស្វែងរក តម្រៀប

បញ្ហា“ រកចំនួនគូក្នុងអារេដែល XOR របស់ពួកគេគឺ ០” ដែលយើងគិតថាយើងបានផ្តល់ អារេ of ចំនួនគត់។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកចំនួនគូដែលមាននៅក្នុងអារេមួយដែលមានគូ Ai XOR Aj = 0 ។

សម្គាល់ៈ ១ តូចជាងឬស្មើ i, i គឺតិចជាង j និង j គឺតូចជាងឬស្មើនឹង n (1 <=i < j<= n) ។

ឧទាហរណ៍

រកចំនួនគូក្នុងអារេដូចជា XOR របស់ពួកគេគឺ ០

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

ការពន្យល់

សន្ទស្សន៍ (០,៤) និង (១.៣) ។

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

ក្បួនដោះស្រាយ

  1. ស្វែងយល់ពីធាតុអតិបរិមាដែលមាននៅក្នុងអារេ។
  2. បង្កើតអារេនៃទំហំ (ធាតុអតិបរមា) ។
  3. ឆ្លងកាត់អារេខណៈពេលដែលខ្ញុំ <n (ប្រវែងអារេ) ។
    1. រាប់និងទុកប្រេកង់នៃធាតុអារេនីមួយៗនៅក្នុងអារេដែលយើងបានបង្កើត។
  4. ឆ្លងកាត់អារេរាប់ខណៈពេលដែលខ្ញុំ <= ធាតុអតិបរមា។
    1. តើលទ្ធផល = លទ្ធផល + រាប់ [i] * (រាប់ [ខ្ញុំ] - 1);
  5. ត្រឡប់លទ្ធផល / ២ ។

ការពន្យល់

យើងមានចំនួនគត់នៃចំនួនគត់។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យរកឃើញគូដែលមានវត្តមាននៅក្នុងអារេបែបនេះ Ai XOR Aj = ០ យើងនឹងប្រើការផ្គូផ្គងការធ្វើផែនទីដែលមានន័យថាយើងនឹងរាប់ប្រេកង់នៃធាតុអារេនីមួយៗដែលយើងអាចរកឃើញប្រសិនបើពួកគេអាចរាប់ [i] * រាប់ [i-0] និងជាលទ្ធផល លទ្ធផល។ ដើម្បីដោះស្រាយការប្រើប្រាស់នេះ អារេ ហើយនៅកន្លែងនោះនៃធាតុអារេដែលដើរតួជាសន្ទស្សន៍នៃចំនួនរាប់ដែលយើងនឹងរក្សាទុកប្រេកង់ធាតុរបស់យើងដូច្នេះប្រសិនបើលេខមួយត្រូវបានរកឃើញនៅកន្លែងជាក់លាក់មួយយើងនឹងប្រើវាជាសន្ទស្សន៍។

យើងនឹងរកឃើញធាតុអតិបរិមាពីអារេ។ ហើយទំហំធាតុអតិបរិមានោះយើងនឹងធ្វើអារេនេះគឺរាប់អារេនេះយើងនឹងប្រើជាអារេប្រេកង់។ យើងត្រូវឆ្លងកាត់អារេនិងរក្សាទុកចំនួននៃធាតុអារេនីមួយៗ។ បន្ទាប់មកយើងនឹងកំណត់អថេរលទ្ធផលទៅ ០ ។

ចូរយើងពិចារណាឧទាហរណ៍មួយ៖

ឧទាហរណ៍

មកដល់ [] = {២, ៣, ១, ៣, ២} ទំហំអតិបរមានៃអារេនឹងមាន ៣ ។

ខ្ញុំ = ០, មកដល់ [ខ្ញុំ] = ២, យើងនឹងរាប់ [arr [ខ្ញុំ]] + = ១, វាមានន័យថាសន្ទស្សន៍ទី ២ នៃធាតុរបស់រាប់នឹងកើនឡើង ១ ។

ខ្ញុំ = ០, មកដល់ [ខ្ញុំ] = ២, យើងនឹងរាប់ [arr [ខ្ញុំ]] + = ១, វាមានន័យថាសន្ទស្សន៍ទី ២ នៃធាតុរបស់រាប់នឹងកើនឡើង ១ ។

i = 2, arr [i] = 1, យើងនឹងរាប់ [arr [ខ្ញុំ]] + = 1, វាមានន័យថាសន្ទស្សន៍ទី ១ នៃធាតុរបស់រាប់នឹងកើនឡើង ១ ។

ខ្ញុំ = ៣, មកដល់ [ខ្ញុំ] = ៣, យើងនឹងរាប់ [អា [អាយ] ខ្ញុំ + = ១, វាមានន័យថាសន្ទស្សន៍ទី ៣ នៃធាតុរបស់រាប់នឹងកើនឡើង ១ ។

ខ្ញុំ = ០, មកដល់ [ខ្ញុំ] = ២, យើងនឹងរាប់ [arr [ខ្ញុំ]] + = ១, វាមានន័យថាសន្ទស្សន៍ទី ២ នៃធាតុរបស់រាប់នឹងកើនឡើង ១ ។

យើងមានអារេរាប់ដូចជារាប់ [] = {0,1,2,2}

យើងនឹងឆ្លងកាត់អារេនេះហើយរាល់ពេលដែលយើងធ្វើលទ្ធផល = លទ្ធផល + រាប់ [i] * (រាប់ [ខ្ញុំ] - ១) ។

ហើយវានឹងត្រឡប់លទ្ធផលដូចលទ្ធផល / ២ ។

លេខកូដ C ++ ដើម្បីរកចំនួនគូក្នុងអារេដូចជា XOR របស់ពួកគេគឺ ០

#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 របស់ពួកគេគឺ ០

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” គឺជាចំនួនធាតុក្នុងអារេ។ O (1) ពេលវេលាត្រូវបានទាមទារសម្រាប់ការចូលប្រើធាតុនៅក្នុងអារេ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺលីនេអ៊ែរ។

ភាពស្មុគស្មាញនៃលំហ

អូ (អតិបរមា), ដែល Max ជាធាតុអតិបរិមាក្នុងចំណោមធាតុទាំងអស់នៅក្នុងអារេ។