ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಜೋಡಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹುಡುಕಿ ಅಂದರೆ ಅವುಗಳ XOR 0


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಕ್ಯಾಡೆನ್ಸ್ ಇಂಡಿಯಾ ಕೂಪನ್‌ಡೂನಿಯಾ ಹನಿವೆಲ್ ವಾಸ್ತವವಾಗಿ ಮಾಹಿತಿ ಎಡ್ಜ್ ಮೂನ್‌ಫ್ರಾಗ್ ಲ್ಯಾಬ್‌ಗಳು pinterest
ಅರೇ ಬಿಟ್ಸ್ ಹ್ಯಾಶ್ ಹುಡುಕಲಾಗುತ್ತಿದೆ ವಿಂಗಡಿಸಲಾಗುತ್ತಿದೆ

"ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಜೋಡಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹುಡುಕಿ, ಅವುಗಳ XOR 0" ಎಂಬ ಸಮಸ್ಯೆ ose ಹಿಸುತ್ತದೆ, ನಾವು ಅದನ್ನು ನೀಡಿದ್ದೇವೆ ಸರಣಿ 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. ನಾನು <n (ರಚನೆಯ ಉದ್ದ) ಆದರೆ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಿರಿ.
    1. ನಾವು ರಚಿಸಿದ ರಚನೆಯಲ್ಲಿ ಪ್ರತಿ ರಚನೆಯ ಅಂಶದ ಆವರ್ತನಗಳನ್ನು ಎಣಿಸಿ ಮತ್ತು ಸಂಗ್ರಹಿಸಿ.
  4. ಎಣಿಕೆ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಿರಿ, ಆದರೆ ನಾನು <= ಗರಿಷ್ಠ ಅಂಶ.
    1. Output ಟ್ಪುಟ್ = output ಟ್ಪುಟ್ + ಎಣಿಕೆ [i] * (ಎಣಿಕೆ [i] - 1) ಮಾಡಿ;
  5. ರಿಟರ್ನ್ output ಟ್ಪುಟ್ / 2.

ವಿವರಣೆ

ನಮ್ಮಲ್ಲಿ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಿದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಜೋಡಿಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ Ai ಉಚಿತ Aj = 0. ನಾವು ಸೂಚ್ಯಂಕ ಮ್ಯಾಪಿಂಗ್ ಅನ್ನು ಬಳಸಲಿದ್ದೇವೆ, ಇದರರ್ಥ ನಾವು ಪ್ರತಿ ರಚನೆಯ ಅಂಶದ ಆವರ್ತನವನ್ನು ಎಣಿಸಲಿದ್ದೇವೆ ಅಂದರೆ ಅವುಗಳು ಎಣಿಕೆ [i] * ಎಣಿಕೆ [i-1] ಮತ್ತು ಅದರ ಪರಿಣಾಮವಾಗಿ .ಟ್ಪುಟ್. ಈ ಬಳಕೆಯನ್ನು ಪರಿಹರಿಸಲು ಒಂದು ಸರಣಿ ಮತ್ತು ನಮ್ಮ ಅಂಶಗಳ ಆವರ್ತನವನ್ನು ನಾವು ಸಂಗ್ರಹಿಸಲಿರುವ ಎಣಿಕೆ ರಚನೆಯ ಸೂಚ್ಯಂಕವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ರಚನೆಯ ಅಂಶದ ಸ್ಥಳದಲ್ಲಿ, ಆದ್ದರಿಂದ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸ್ಥಳದಲ್ಲಿ ಒಂದು ಸಂಖ್ಯೆ ಕಂಡುಬಂದರೆ, ನಾವು ಅದನ್ನು ಸೂಚ್ಯಂಕವಾಗಿ ಬಳಸಲಿದ್ದೇವೆ.

ನಾವು ರಚನೆಯಿಂದ ಗರಿಷ್ಠ ಅಂಶವನ್ನು ಕಾಣುತ್ತೇವೆ. ಮತ್ತು ಆ ಗರಿಷ್ಠ ಅಂಶದ ಗಾತ್ರದಲ್ಲಿ, ನಾವು ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಮಾಡಲು ಹೊರಟಿದ್ದೇವೆ, ಇದು ಎಣಿಕೆ ರಚನೆಯಾಗಿದೆ, ಇದನ್ನು ನಾವು ಆವರ್ತನ ರಚನೆಯಾಗಿ ಬಳಸಲಿದ್ದೇವೆ. ನಾವು ರಚನೆಯ ಮೂಲಕ ಹಾದುಹೋಗಬೇಕು ಮತ್ತು ಪ್ರತಿ ರಚನೆಯ ಅಂಶದ ಎಣಿಕೆಯನ್ನು ಸಂಗ್ರಹಿಸಬೇಕು. ನಂತರ ನಾವು variable ಟ್ಪುಟ್ ವೇರಿಯಬಲ್ ಅನ್ನು 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}

ನಾವು ಈ ಶ್ರೇಣಿಯನ್ನು ದಾಟುತ್ತೇವೆ, ಮತ್ತು ಪ್ರತಿ ಬಾರಿ ನಾವು output ಟ್‌ಪುಟ್ = + ಟ್‌ಪುಟ್ + ಎಣಿಕೆ [i] * (ಎಣಿಕೆ [i] - 1) ಮಾಡುತ್ತೇವೆ.

ಮತ್ತು ಅದು output ಟ್‌ಪುಟ್ ಅನ್ನು 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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ರಚನೆಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಪ್ರವೇಶಿಸಲು ಒ (1) ಸಮಯ ಬೇಕಾಗುತ್ತದೆ. ಹೀಗಾಗಿ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಗರಿಷ್ಠ), ಅಲ್ಲಿ ರಚನೆಯ ಎಲ್ಲಾ ಅಂಶಗಳಲ್ಲಿ ಮ್ಯಾಕ್ಸ್ ಗರಿಷ್ಠ ಅಂಶವಾಗಿದೆ.