Рубрики

XOR всех подмассивов XOR | Комплект 1

Учитывая массив целых чисел, нам нужно получить полный XOR всех XOR подмассива, где XOR подмассива может быть получен путем XORing всех его элементов.

Примеры :

Input : arr[] = [3, 5, 2, 4, 6]
Output : 7
Total XOR of all subarray XORs is,
(3) ^ (5) ^ (2) ^ (4) ^ (6)
(3^5) ^ (5^2) ^ (2^4) ^ (4^6)
(3^5^2) ^ (5^2^4) ^ (2^4^6)
(3^5^2^4) ^ (5^2^4^6) ^
(3^5^2^4^6) = 7     

Input : arr[] = {1, 2, 3}
Output : 2

Input : arr[] = {1, 2, 3, 4}
Output : 0

Простое решение — сгенерировать все подмассивы и вычислить XOR для всех из них. Ниже приведена реализация вышеуказанной идеи:

C ++

// C ++ программа для получения полного xor всех подмассивных xors
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает XOR всех подрешеток xors

int getTotalXorOfSubarrayXors(int arr[], int N)

{

    // инициализировать результат 0 как (xor 0 = a)

    int res = 0;

  

    // выбираем начальный элемент

    for (int i=0; i<N; i++)

  

        // выбираем элемент eNding

        for (int j=i; j<N; j++)

  

            // Делаем XOR элементов в текущем подмассиве

            for (int k=i; k<=j; k++)

                res = res ^ arr[k];

  

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int arr[] = {3, 5, 2, 4, 6};

    int N = sizeof(arr) / sizeof(arr[0]);

  

    cout << getTotalXorOfSubarrayXors(arr, N);

    return 0;

}

Джава

// Java-программа для получения полного XOR
// всех подрешеток xors

public class GFG {

          

    // Возвращает XOR всех подрешеток xors

    static int getTotalXorOfSubarrayXors(

                          int arr[], int N)

    {

          

        // инициализировать результат

        // 0 as (a xor 0 = a)

        int res = 0;

          

        // выбираем начальный элемент

        for (int i = 0; i < N; i++)

          

            // выбираем элемент eNding

            for (int j = i; j < N; j++)

          

            // Делаем XOR элементов

            // в текущем подмассиве

            for (int k = i; k <= j; k++)

                res = res ^ arr[k];

      

        return res;

    }

      

    // Код драйвера

    public static void main(String args[])

    {

        int arr[] = {3, 5, 2, 4, 6};

        int N = arr.length;

          

        System.out.println(

            getTotalXorOfSubarrayXors(arr, N));

    }

}

  
// Этот код предоставлен Sam007.

Python 3

# Python программа для получения общего xor
# всех подрешеток xors

  
# Возвращает XOR всех подрешеток xors

def getTotalXorOfSubarrayXors(arr, N):

      

    # инициализировать результат как 0

    # (xor 0 = a)

    res = 0

  

    # выберите начальный элемент

    for i in range(0, N):

          

        # выберите элемент eNding

        for j in range(i, N):

              

            # Делать XOR элементов в

            # текущий подмассив

            for k in range(i, j + 1):

                res = res ^ arr[k]

              

    return res

  
# Код драйвера для тестирования вышеуказанных методов

arr = [3, 5, 2, 4, 6]

N = len(arr)

  

print(getTotalXorOfSubarrayXors(arr, N))

  
# Этот код предоставлен Sam007.

C #

// C # программа для получения полного XOR
// всех подрешеток xors

using System;

  

class GFG {

  
// Возвращает XOR всех подрешеток xors

static int getTotalXorOfSubarrayXors(int []arr, 

                                     int N)

{

      
// инициализировать результат
// 0 as (a xor 0 = a)

int res = 0;

  
// выбираем начальный элемент

for (int i = 0; i < N; i++)

  

    // выбираем элемент eNding

    for (int j = i; j < N; j++)

  

        // Делаем XOR элементов

        // в текущем подмассиве

        for (int k = i; k <= j; k++)

            res = res ^ arr[k];

  

return res;

}

  
// Код драйвера

static void Main()

{

    int []arr = {3, 5, 2, 4, 6};

    int N = arr.Length;

    Console.Write(getTotalXorOfSubarrayXors(arr, N));

}
}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для получения итогов
// xor всех подрешеток xors

  
// Возвращает XOR всех подрешеток xors

function getTotalXorOfSubarrayXors($arr, $N)

{

      

    // инициализировать результат

    // 0 as (a xor 0 = a)

    $res = 0;

  

    // выбираем начальный элемент

    for($i = 0; $i < $N; $i++)

  

        // выбираем элемент eNding

        for($j = $i; $j < $N; $j++)

  

            // Делаем XOR элементов в

            // текущий подмассив

            for($k = $i; $k <= $j; $k++)

                $res = $res ^ $arr[$k];

  

    return $res;

}

  

    // Код драйвера

    $arr = array(3, 5, 2, 4, 6);

    $N = sizeof($arr);

    echo getTotalXorOfSubarrayXors($arr, $N);

  
// Этот код предоставлен нитин митталь.
?>

Выход:

7

Сложность времени: O (N 3 )

Эффективное решение основано на идее перечисления всех подмассивов, мы можем подсчитать частоту каждого элемента, произошедшего полностью во всех подмассивах, если частота элемента нечетна, то она будет включена в конечный результат, иначе нет.

As in above example, 
3 occurred 5 times,
5 occurred 8 times,
2 occurred 9 times,
4 occurred 8 times,
6 occurred 5 times
So our final result will be xor of all elements which occurred odd number of times
i.e. 3^2^6 = 7

From above occurrence pattern we can observe that number at i-th index will have 
(i + 1) * (N - i) frequency. 

Таким образом, мы можем выполнить итерацию по всем элементам один раз и вычислить их частоты, и если это нечетно, мы можем включить это в наш конечный результат, XOR его с результатом.
Общая временная сложность решения будет O (N)

C ++

// C ++ программа для получения итогов
// xor всех подрешеток xors
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает XOR всех подрешеток xors

int getTotalXorOfSubarrayXors(int arr[], 

                              int N)

{

    // инициализировать результат 0

    // as (XOR 0 = a)

    int res = 0;

  

    // зациклить все элементы один раз

    for (int i = 0; i < N; i++)

    {

        // получаем частоту

        // текущий элемент

        int freq = (i + 1) * (N - i);

  

        // Раскомментируем ниже строки для печати

        // частота обр [я]

        // cout << arr [i] << "" << freq << endl;

  

        // если частота нечетная, то

        // включить его в результат

        if (freq % 2 == 1)

            res = res ^ arr[i];

    }

  

    // вернуть результат

    return res;

}

  
// Код драйвера

int main()

{

    int arr[] = {3, 5, 2, 4, 6};

    int N = sizeof(arr) / sizeof(arr[0]);

  

    cout << getTotalXorOfSubarrayXors(arr, N);

    return 0;

}

Джава

// Java-программа для получения общего XOR
// всех подрешеток xors

import java.io.*;

  

public class GFG {

      

    // Возвращает XOR всего подмассива

    // xors

    static int getTotalXorOfSubarrayXors(

                          int arr[], int N)

    {

          

        // инициализировать результат 0

        // as (XOR 0 = a)

        int res = 0;

      

        // зациклить все элементы один раз

        for (int i = 0; i < N; i++)

        {

            // получаем частоту

            // текущий элемент

            int freq = (i + 1) * (N - i);

      

            // Раскомментируем ниже строки для печати

            // частота обр [я]

              

            // если частота нечетная, то

            // включить его в результат

            if (freq % 2 == 1)

                res = res ^ arr[i];

        }

      

        // вернуть результат

        return res;

    }

      

    public static void main(String[] args)

    {

  

        int arr[] = {3, 5, 2, 4, 6};

        int N = arr.length;

        System.out.println(

            getTotalXorOfSubarrayXors(arr, N));

    }

}

  
// Этот код предоставлен Sam007.

Python 3

# Python3 программа для получения итогов
# xor всех подмассивов xors

  
# Возвращает XOR всех
# subarray xors

def getTotalXorOfSubarrayXors(arr, N):

  

    # инициализировать результат 0

    # as (XOR 0 = a)

    res = 0

  

    # перебрать все элементы один раз

    for i in range(0, N):

      

        # получить частоту

        # текущий элемент

        freq = (i + 1) * (N - i)

  

        # Раскомментируйте ниже строки для печати

        # частота обр [я]

  

        # если частота нечетная, то

        # включить его в результат

        if (freq % 2 == 1):

            res = res ^ arr[i]

      

    # вернуть результат

    return res

  
Код водителя

arr = [3, 5, 2, 4, 6]

N = len(arr) 

print(getTotalXorOfSubarrayXors(arr, N))

      
# Этот код добавлен
# от Smitha

C #

// C # программа для получения общего xor
// всех подрешеток xors

using System;

  

class GFG

{
// Возвращает XOR всех подрешеток xors

static int getTotalXorOfSubarrayXors(int []arr, 

                                     int N)

{

    // инициализировать результат 0

    // as (XOR 0 = a)

    int res = 0;

  

    // зациклить все элементы один раз

    for (int i = 0; i < N; i++)

    {

        // получаем частоту

        // текущий элемент

        int freq = (i + 1) * (N - i);

  

        // Раскомментируем ниже строки для печати

        // частота обр [я]

          

        // если частота нечетная, то

        // включить его в результат

        if (freq % 2 == 1)

            res = res ^ arr[i];

    }

  

    // вернуть результат

    return res;

}

      

    // Код драйвера

    public static void Main()

    {

    int []arr = {3, 5, 2, 4, 6};

    int N = arr.Length;

  

    Console.Write(getTotalXorOfSubarrayXors(arr, N));

    }

}

      

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для получения итогов
// xor всех подрешеток xors

  
// Возвращает XOR всех подрешеток xors

function getTotalXorOfSubarrayXors($arr

                                   $N)

{

      

    // инициализировать результат 0

    // as (XOR 0 = a)

    $res = 0;

  

    // зациклить все элементы один раз

    for ($i = 0; $i < $N; $i++)

    {

          

        // получаем частоту

        // текущий элемент

        $freq = ($i + 1) * ($N - $i);

  

        // если частота нечетная, то

        // включить его в результат

        if ($freq % 2 == 1)

            $res = $res ^ $arr[$i];

    }

  

    // вернуть результат

    return $res;

}

  

    // Код драйвера

    $arr = array(3, 5, 2, 4, 6);

    $N = count($arr);

  

    echo getTotalXorOfSubarrayXors($arr, $N);

  
// Этот код предоставлен anuj_67.
?>

Выход :

7

Сложность времени: O (N)

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

XOR всех подмассивов XOR | Комплект 1

0.00 (0%) 0 votes