Рубрики

Подсчитать количество подмассивов с данным XOR

Учитывая массив целых чисел arr [] и число m, подсчитайте количество подмассивов с XOR их элементов как m.

Примеры:

Input : arr[] = {4, 2, 2, 6, 4}, m = 6
Output : 4
Explanation : The subarrays having XOR of 
              their elements as 6 are {4, 2}, 
              {4, 2, 2, 6, 4}, {2, 2, 6},
               and {6}

Input : arr[] = {5, 6, 7, 8, 9}, m = 5
Output : 2
Explanation : The subarrays having XOR of
              their elements as 2 are {5}
              and {5, 6, 7, 8, 9}

Простое решение состоит в том, чтобы использовать два цикла, чтобы пройти через все возможные подмассивы arr [] и посчитать количество подмассивов, имеющих XOR их элементов, как m.

C ++

// Простая программа на C ++ для подсчета всех подмассивов, имеющих
// XOR элементов по заданному значению m
#include <bits/stdc++.h>

using namespace std;

  
// Простая функция, которая возвращает количество подмассивов
// обр со значением XOR равным m

long long subarrayXor(int arr[], int n, int m)

{

    long long ans = 0; // Инициализация ANS

  

    // Выбрать начальную точку i для подмассивов

    for (int i = 0; i < n; i++) {

        int xorSum = 0; // Сохраняем XOR текущего подмассива

  

        // Выбираем конечную точку j подмассива для каждого i

        for (int j = i; j < n; j++) {

            // вычисляем xorSum

            xorSum = xorSum ^ arr[j];

  

            // Если xorSum равен заданному значению,

            // увеличить ответ на 1.

            if (xorSum == m)

                ans++;

        }

    }

    return ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

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

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

    int m = 6;

  

    cout << "Number of subarrays having given XOR is "

         << subarrayXor(arr, n, m);

    return 0;

}

Джава

// Простая Java-программа для подсчета всех
// подмассивы, имеющие XOR элементов
// как заданное значение m

public class GFG {

  

    // Простая функция, которая возвращает

    // подсчет массивов обр

    // значение XOR равно m

    static long subarrayXor(int arr[],

                             int n, int m)

    {

          

        // Инициализация ANS

        long ans = 0;

  

        // Выберите начальную точку i из

        // подмассивы

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

        {

              

            // Сохраняем XOR текущего

            // подрешетка

            int xorSum = 0;

  

            // Выберите конечную точку j из

            // подрешетка для каждого я

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

            {

                  

                // вычисляем xorSum

                xorSum = xorSum ^ arr[j];

  

                // Если xorSum равен

                // заданное значение, увеличение

                // ответ по 1.

                if (xorSum == m)

                    ans++;

            }

        }

          

        return ans;

    }

  

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

    public static void main(String args[])

    {

  

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

        int n = arr.length;

        int m = 6;

  

        System.out.println("Number of subarrays"

                       + " having given XOR is "

                       + subarrayXor(arr, n, m));

    }

}

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

python3

      
# Простая программа Python3 для подсчета всех подмассивов, имеющих
# XOR элементов по заданному значению m

   
# Простая функция, которая возвращает количество подмассивов
№ обр со значением XOR, равным м

def subarrayXor(arr, n, m):

    ans = 0 # Инициализировать ANS

   

    # Выберите начальную точку для подмассивов

    for i in range(0,n):

          

        xorSum = 0 # Сохранить XOR текущего подмассива

   

        # Выберите окончание po j подмассива для каждого i

        for in range(i,n):

            # рассчитать xorSum

            xorSum = xorSum ^ arr[j]

   

            # Если xorSum равно заданному значению,

            # увеличить ответ на 1.

            if (xorSum == m):

                ans+=1

    return ans

   
# Программа драйвера для проверки вышеуказанной функции

def main():

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

    n = len(arr)

    m = 6

   

    print("Number of subarrays having given XOR is "

         , subarrayXor(arr, n, m))

  

if __name__ == '__main__':

    main()

      
# этот код предоставлен 29AjayKumar

C #

// Простая программа на C # для подсчета всех
// подмассивы, имеющие XOR элементов
// как заданное значение m

using System;

  

class GFG {

      

    // Простая функция, которая возвращает

    // подсчет массивов обр

    // со значением XOR равным m

    static long subarrayXor(int[] arr,

                            int n, int m)

    {

          

        // Инициализация ANS

        long ans = 0;

  

        // Выберите начальную точку i из

        // подмассивы

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

        {

              

            // Сохраняем XOR текущего

            // подрешетка

            int xorSum = 0;

  

            // Выберите конечную точку j из

            // подрешетка для каждого я

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

            {

                  

                // вычисляем xorSum

                xorSum = xorSum ^ arr[j];

  

                // Если xorSum равен

                // заданное значение, увеличение

                // ответ по 1.

                if (xorSum == m)

                    ans++;

            }

        }

          

        return ans;

    }

  

    // Программа для водителя

    public static void Main()

    {

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

        int n = arr.Length;

        int m = 6;

  

        Console.Write("Number of subarrays"

                  + " having given XOR is "

                  + subarrayXor(arr, n, m));

    }

}

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

PHP

<?php
// Простая программа PHP для
// подсчитать все подмассивы, имеющие
// XOR элементов по заданному значению m

  
// Простая функция, которая возвращает
// подсчет массивов обр
// со значением XOR равным m

function subarrayXor($arr, $n,$m)

{

      

    // Инициализация ANS

    $ans = 0; 

  

    // Выберите начальную точку

    // я подмассивов

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

    {

          

        // Сохраняем XOR

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

        $xorSum = 0; 

  

        // Выберите конечную точку j из

        // подрешетка для каждого я

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

        {

            // вычисляем xorSum

            $xorSum = $xorSum ^ $arr[$j];

  

            // Если xorSum равен

            // до заданного значения,

            // увеличить ответ на 1.

            if ($xorSum == $m)

                $ans++;

        }

    }

    return $ans;

}

  

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

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

    $n = count($arr);

    $m = 6;

  

    echo "Number of subarrays having given XOR is "

         , subarrayXor($arr, $n, $m);

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


Выход:

Number of subarrays having given XOR is 4

Сложность времени вышеупомянутого решения составляет O (n 2 ).

Эффективное решение решает вышеуказанную проблему за O (n) время. Давайте назовем XOR всех элементов в диапазоне [i + 1, j] как A, в диапазоне [0, i] как B и в диапазоне [0, j] как C. Если мы сделаем XOR из B с C перекрывающиеся элементы в [0, i] из B и C обнуляются, и мы получаем XOR всех элементов в диапазоне [i + 1, j], т.е. A. Так как A = B XOR C, мы имеем B = A XOR C. Теперь, если мы знаем значение C и принимаем значение A за m, мы получаем количество A как количество всех B, удовлетворяющих этому соотношению. По сути, мы получаем количество всех подмассивов, имеющих XOR-сумму m для каждого C. Когда мы берем сумму этого числа по всем C, мы получаем наш ответ.

1) Initialize ans as 0.
2) Compute xorArr, the prefix xor-sum array.
3) Create a map mp in which we store count of 
   all prefixes with XOR as a particular value. 
4) Traverse xorArr and for each element in xorArr
   (A) If m^xorArr[i] XOR exists in map, then 
       there is another previous prefix with 
       same XOR, i.e., there is a subarray ending
       at i with XOR equal to m. We add count of
       all such subarrays to result. 
   (B) If xorArr[i] is equal to m, increment ans by 1.
   (C) Increment count of elements having XOR-sum 
       xorArr[i] in map by 1.
5) Return ans.

C ++

// C ++ Программа для подсчета всех подмассивов, имеющих
// XOR элементов с заданным значением m с
// O (n) временная сложность.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество подмассивов arr с XOR
// значение равно m

long long subarrayXor(int arr[], int n, int m)

{

    long long ans = 0; // Инициализировать ответ, который будет возвращен

  

    // Создаем массив префиксов xor-sum таким образом, чтобы

    // xorArr [i] имеет значение, равное XOR

    // всех элементов в arr [0 ..... i]

    int* xorArr = new int[n];

  

    // Создать карту, в которой хранится номер префиксного массива

    // элементы, соответствующие значению XOR

    unordered_map<int, int> mp;

  

    // Инициализируем первый элемент массива префиксов

    xorArr[0] = arr[0];

  

    // Вычисляем массив префиксов.

    for (int i = 1; i < n; i++)

        xorArr[i] = xorArr[i - 1] ^ arr[i];

  

    // Рассчитать ответ

    for (int i = 0; i < n; i++) {

        // Находим XOR текущего префикса с m.

        int tmp = m ^ xorArr[i];

  

        // Если выше XOR существует в карте, то есть

        // другой предыдущий префикс с тем же

        // XOR, то есть есть окончание подмассива

        // у i с XOR, равным m.

        ans = ans + ((long long)mp[tmp]);

  

        // Если этот подмассив имеет XOR, равный самому m.

        if (xorArr[i] == m)

            ans++;

  

        // Добавить XOR этого подмассива на карту

        mp[xorArr[i]]++;

    }

  

    // Возвращаем общее количество подмассивов с XOR

    // элементы с заданным значением m

    return ans;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

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

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

    int m = 6;

  

    cout << "Number of subarrays having given XOR is "

         << subarrayXor(arr, n, m);

    return 0;

}

python3

# Python3 Программа для подсчета всех подмассивов
# имеющий XOR элементов в качестве заданного значения m
# с O (n) сложностью по времени.

  
# Возвращает количество подмассивов обр
# со значением XOR равным m

def subarrayXor(arr, n, m):

  

    ans = 0 # Инициализировать ответ, который будет возвращен

  

    # Создайте префиксный массив xor-sum так, чтобы

    # xorArr [i] имеет значение, равное XOR

    # всех элементов в arr [0 ..... i]

    xorArr =[0 for _ in range(n)]

  

    # Создать карту, в которой хранится номер префиксного массива

    # элементы, соответствующие значению XOR

    mp = dict()

  

    # Инициализировать первый элемент

    # префиксного массива

    xorArr[0] = arr[0]

  

    # Вычисление префиксного массива.

    for i in range(1, n):

        xorArr[i] = xorArr[i - 1] ^ arr[i]

  

    # Рассчитать ответ

    for i in range(n):

          

        # Найти XOR текущего префикса с помощью m.

        tmp = m ^ xorArr[i]

  

        # Если выше XOR существует на карте, то есть

        # другой предыдущий префикс с тем же

        # XOR, то есть есть окончание подмассива

        # у меня с XOR, равным м.

        if tmp in mp.keys():

            ans = ans + (mp[tmp])

  

        # Если у этого подмассива есть XOR

        # равно м сам.

        if (xorArr[i] == m):

            ans += 1

  

        # Добавьте XOR этого подмассива на карту

        mp[xorArr[i]] = mp.get(xorArr[i], 0) + 1

  

    # Возвращаем общее количество подмассивов, имеющих

    # XOR элементов по заданному значению m

    return ans

  
Код водителя

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

n = len(arr)

m = 6

  

print("Number of subarrays having given XOR is",

                        subarrayXor(arr, n, m))

  
# Этот код предоставлен Мохит Кумар

Выход:

Number of subarrays having given XOR is 4

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

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

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

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

Подсчитать количество подмассивов с данным XOR

0.00 (0%) 0 votes