Рубрики

Сумма XOR всех пар в массиве

Для данного массива из n целых чисел найдите сумму xor всех пар чисел в массиве.

Примеры :

Input : arr[] = {7, 3, 5}
Output : 12
7 ^ 3 = 4
3 ^ 5 = 6
7 ^ 5 = 2
Sum = 4 + 6 + 2 
    = 12

Input : arr[] = {5, 9, 7, 6}
Output : 47
5 ^ 9 = 12
9 ^ 7 = 14
7 ^ 6 = 1
5 ^ 7 = 2
5 ^ 6 = 3
9 ^ 6 = 15
Sum = 12 + 14 + 1 + 2 + 3 + 15
    = 47

Наивное решение
Подход грубой силы заключается в запуске двух циклов, а временная сложность равна O (n 2 ).

C ++

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

using namespace std;

  
// Возвращает сумму побитового ИЛИ
// всех пар

int pairORSum(int arr[], int n)

{

    int ans = 0; // Инициализировать результат

  

    // Рассмотрим все пары (arr [i], arr [j) такие, что

    // я <j

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

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

            ans += arr[i] ^ arr[j];

  

    return ans;

}

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

int main()

{

    int arr[] = { 5, 9, 7, 6 };

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

    cout << pairORSum(arr, n) << endl;

    return 0;

}

Джава

// Простая Java-программа для вычисления
// сумма побитового ИЛИ всех пар

import java.io.*;

  

class GFG {

      

              

    // Возвращает сумму побитового ИЛИ

    // всех пар

    static int pairORSum(int arr[], int n)

    {

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

        int ans = 0

      

        // Рассмотрим все пары (arr [i], arr [j)

        // такой, что я <j

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

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

                ans += arr[i] ^ arr[j];

      

        return ans;

    }

  

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

    public static void main (String[] args) {

     

        int arr[] = { 5, 9, 7, 6 };

        int n = arr.length;

          

        System.out.println(pairORSum(arr,

                                arr.length));

    }

}

  

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

python3

# Простая программа на Python 3 для вычисления
# сумма побитового ИЛИ всех пар

  
# Возвращает сумму побитового ИЛИ
количество всех пар

def pairORSum(arr, n) :

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

  

    # Рассмотрим все пары (arr [i], arr [j)

    # такое, что я <j

    for i in range(0, n) :

          

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

              

            ans = ans + (arr[i] ^ arr[j])

              

    return ans

      

  
Код водителя

arr = [ 5, 9, 7, 6 ]

n = len(arr)

  

print(pairORSum(arr, n))

  

  

  
# Этот код предоставлен Никитой Тивари.

C #

// Простая программа на C # для вычисления
// сумма побитового ИЛИ всех пар

using System;

  

class GFG {

      

              

    // Возвращает сумму побитового ИЛИ

    // всех пар

    static int pairORSum(int []arr, int n)

    {

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

        int ans = 0; 

      

        // Рассмотрим все пары (arr [i], arr [j)

        // такой, что я <j

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

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

                ans += arr[i] ^ arr[j];

      

        return ans;

    }

  

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

    public static void Main () {

      

        int []arr = { 5, 9, 7, 6 };

        int n = arr.Length;

          

        Console.WriteLine(pairORSum(arr,

                                arr.Length));

    }

}

  

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

PHP

<?php
// Простая PHP-программа для вычисления
// сумма побитового ИЛИ всех пар

  
// Возвращает сумму побитового ИЛИ
// всех пар

function pairORSum($arr, $n)

{

      

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

    $ans = 0; 

  

    // Рассмотрим все пары

    // (arr [i], arr [j) такой, что

    // я <j

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

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

            $ans += $arr[$i] ^ $arr[$j];

  

    return $ans;

}

  

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

    $arr = array( 5, 9, 7, 6 );

    $n = count($arr);

    echo pairORSum($arr, $n) ;

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

Выход :

47

Эффективное решение
Эффективное решение может решить эту проблему за O (n) время. Здесь предполагается, что целые числа представлены с использованием 32 бит.
Оптимизированным решением будет попытка манипулирования битами . Чтобы реализовать решение, мы рассмотрим все биты, которые равны 1, а которые равны 0, и сохраняем их количество в двух разных переменных. Затем умножьте эти числа вместе со степенью 2, поднятой в эту позицию бита. Сделайте это для всех битовых позиций чисел. Их сумма будет нашим ответом.

Explanation :  arr[] = { 7, 3, 5 }
7 = 1 1 1
3 = 0 1 1
5 = 1 0 1
For bit position 0 : 
Bits with zero = 0
Bits with one = 3
Answer = 0 * 3 * 2 ^ 0 = 0
Similarly, for bit position 1 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 1 = 4
Similarly, for bit position 2 :
Bits with zero = 1
Bits with one = 2
Answer = 1 * 2 * 2 ^ 2 = 8
 Final answer = 0 + 4 + 8 = 12 

CPP

// Эффективная программа C ++ для вычисления
// сумма побитового ИЛИ всех пар
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает сумму побитового ИЛИ
// всех пар

long long int sumXOR(int arr[], int n)

{

    long long int sum = 0;

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

    {

        // Подсчет нулей и единиц

        int zc = 0, oc = 0; 

          

        // Индивидуальная сумма в каждой битовой позиции

        long long int idsum = 0; 

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

        {

            if (arr[j] % 2 == 0)

                zc++;

            else

                oc++;

            arr[j] /= 2;

        }

          

        // вычисление индивидуальной битовой суммы

        idsum = oc * zc * (1 << i); 

  

        // итоговая сумма

        sum += idsum; 

    }

    return sum;

}

  

int main()

{

    long long int sum = 0;

    int arr[] = { 5, 9, 7, 6 };

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

    sum = sumXOR(arr, n);

    cout << sum;

    return 0;

}

Джава

// Эффективная Java-программа для вычисления
// сумма побитового ИЛИ всех пар

import java.io.*;

  

class GFG {

      

    // Возвращает сумму побитового ИЛИ

    // всех пар

    static long sumXOR(int arr[], int n)

    {

        long sum = 0;

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

        {

            // Подсчет нулей и единиц

            int zc = 0, oc = 0

              

            // Индивидуальная сумма в каждой битовой позиции

            long idsum = 0

              

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

            {

                if (arr[j] % 2 == 0)

                    zc++;

                      

                else

                    oc++;

                arr[j] /= 2;

            }

              

            // вычисление индивидуальной битовой суммы

            idsum = oc * zc * (1 << i); 

      

            // итоговая сумма

            sum += idsum; 

        }

        return sum;

    }

      

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

    public static void main(String args[])

    {

        long sum = 0;

        int arr[] = { 5, 9, 7, 6 };

        int n = arr.length;

          

        sum = sumXOR(arr, n);

        System.out.println(sum);

    }

}

  
// Этот код предоставлен Никитой Тивари.

python3

# Эффективная программа Python3 для вычисления
# сумма побитового ИЛИ всей пары

  
# Возвращает сумму побитового ИЛИ
количество всех пар

def sumXOR( arr,  n):

      

    sum = 0

    for i in range(0, 32):

  

        # Количество нулей и единиц

        zc = 0

        oc = 0

           

        # Индивидуальная сумма в каждой битовой позиции

        idsum = 0

        for j in range(0, n):

            if (arr[j] % 2 == 0):

                zc = zc + 1

                  

            else:

                oc = oc + 1

            arr[j] = int(arr[j] / 2)

          

           

        # вычисление индивидуальной битовой суммы

        idsum = oc * zc * (1 << i)

   

        # итоговая сумма

        sum = sum + idsum; 

      

    return sum

  

  

  
# функция драйвера

sum = 0

arr = 5, 9, 7, 6 ]

n = len(arr)

sum = sumXOR(arr, n);

print (sum)

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

C #

// Эффективная программа на C # для вычисления
// сумма побитового ИЛИ всех пар

using System;

  

class GFG {

      

    // Возвращает сумму побитового ИЛИ

    // всех пар

    static long sumXOR(int []arr, int n)

    {

        long sum = 0;

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

        {

            // Подсчет нулей и единиц

            int zc = 0, oc = 0; 

              

            // Индивидуальная сумма в каждой битовой позиции

            long idsum = 0; 

              

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

            {

                if (arr[j] % 2 == 0)

                    zc++;

                      

                else

                    oc++;

                arr[j] /= 2;

            }

              

            // вычисление индивидуальной битовой суммы

            idsum = oc * zc * (1 << i); 

      

            // итоговая сумма

            sum += idsum; 

        }

        return sum;

    }

      

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

    public static void Main()

    {

        long sum = 0;

        int []arr = { 5, 9, 7, 6 };

        int n = arr.Length;

          

        sum = sumXOR(arr, n);

        Console.WriteLine(sum);

    }

}

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

PHP

<?php
// Эффективная программа PHP для вычисления
// сумма побитового ИЛИ всех пар

  
// Возвращает сумму побитового ИЛИ
// всех пар

function sumXOR($arr, $n)

{

    $sum = 0;

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

    {

        // Подсчет нулей и единиц

        $zc = 0; $oc = 0; 

          

        // Индивидуальная сумма на каждом

        // битовая позиция

        $idsum = 0; 

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

        {

            if ($arr[$j] % 2 == 0)

                $zc++;

            else

                $oc++;

                  

            $arr[$j] /= 2;

        }

          

        // вычисление индивидуальной битовой суммы

        $idsum = $oc * $zc * (1 << $i); 

  

        // итоговая сумма

        $sum += $idsum

    }

      

    return $sum;

}

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

    $sum = 0;

    $arr = array( 5, 9, 7, 6 );

    $n = count($arr);

    $sum = sumXOR($arr, $n);

    echo $sum;

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


Выход:

47

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

Сумма XOR всех пар в массиве

0.00 (0%) 0 votes