Рубрики

Сумма побитовых и всех пар в данном массиве

Учитывая массив «arr [0..n-1]» целых чисел, вычислите сумму «arr [i] & arr [j]» для всех пар в данном, где i <j. Здесь & является побитовым оператором AND. Ожидаемая сложность времени O (n).
Примеры :

Input:  arr[] = {5, 10, 15}
Output: 15
Required Value = (5 & 10) + (5 & 15) + (10 & 15) 
               = 0 + 5 + 10 
               = 15

Input: arr[] = {1, 2, 3, 4}
Output: 3
Required Value = (1 & 2) + (1 & 3) + (1 & 4) + 
                 (2 & 3) + (2 & 4) + (3 & 4) 
               = 0 + 1 + 0 + 2 + 0 + 0
               = 3

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

C ++

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

using namespace std;

  
// Возвращает значение "arr [0] & arr [1] + arr [0] & arr [2] +
// ... arr [i] & arr [j] + ..... arr [n-2] & arr [n-1] "

int pairAndSum(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, 10, 15};

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

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

    return 0;

}

Джава

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

import java.io.*;

  

class GFG {

      

    // Возвращает значение "arr [0] & arr [1] +

    // arr [0] & arr [2] + ... arr [i] & arr [j] +

    // ..... arr [n-2] & arr [n-1] "

    static int pairAndSum(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, 10, 15};

        int n = arr.length;

        System.out.println(pairAndSum(arr, n) );

    }

}

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

python3

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

  
# Возвращает значение "arr [0] & arr [1] +
# arr [0] & arr [2] + ... arr [i] & arr [j] +
# ..... arr [n-2] & arr [n-1] "

def pairAndSum(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, 10, 15]

n = len(arr) 

print(pairAndSum(arr, n))

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

C #

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

using System;

  

class GFG {

       

    // Возвращает значение "arr [0] & arr [1] +

    // arr [0] & arr [2] + ... arr [i] & arr [j] +

    // ..... arr [n-2] & arr [n-1] "

    static int pairAndSum(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, 10, 15};

        int n = arr.Length;

        Console.Write(pairAndSum(arr, n) );

    }

}

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

PHP

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

  
// Возвращает значение "arr [0] &
// arr [1] + arr [0] & arr [2] +
// ... arr [i] & arr [j] + .....
// arr [n-2] & arr [n-1] "

  

function pairAndSum($arr, $n)

{

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

    $ans = 0; 

  

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

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

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

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

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

  

    return $ans;

}

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

$arr = array(5, 10, 15);

$n = sizeof($arr) ;

echo pairAndSum($arr, $n), "\n";

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


Выход :

15

Эффективное решение может решить эту проблему за O (n) время. Здесь предполагается, что целые числа представлены с использованием 32 бит.

Идея состоит в том, чтобы посчитать количество установленных битов в каждой i-й позиции (i> = 0 && i <= 31). Любой i-й бит AND двух чисел равен 1, если соответствующий бит в обоих числах равен 1.

Пусть k будет количеством установленных бит в i-й позиции. Общее количество пар с i-ым установленным битом будет k C 2 = k * (k-1) / 2 (Count k означает, что есть k чисел, которые имеют i-ый установленный бит). Каждая такая пара добавляет 2 я к общей сумме. Точно так же мы работаем для всех остальных мест и добавляем сумму к нашему окончательному ответу.

Эта идея похожа на это . Ниже приведена реализация.

С

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

using namespace std;

  
// Возвращает значение "arr [0] & arr [1] + arr [0] & arr [2] +
// ... arr [i] & arr [j] + ..... arr [n-2] & arr [n-1] "

int pairAndSum(int arr[], int n)

{

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

  

    // Обход всех битов

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

    {

        // Подсчитать количество элементов с установленным i-ым битом

        int k = 0;  // Инициализировать счет

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

            if ( (arr[j] & (1 << i)) )

                k++;

  

        // Есть k установленных битов, значит k (k-1) / 2 пары.

        // Каждая пара добавляет 2 ^ i к ответу. Следовательно,

        // мы добавляем «2 ^ i * [k * (k-1) / 2]» к ответу.

        ans += (1<<i) * (k*(k-1)/2);

    }

  

    return ans;

}

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

int main()

{

    int arr[] = {5, 10, 15};

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

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

    return 0;

}

Джава

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

import java.io.*;

  

class GFG {

      

    // Возвращает значение "arr [0] & arr [1] +

    // arr [0] & arr [2] + ... arr [i] & arr [j] +

    // ..... arr [n-2] & arr [n-1] "

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

    {

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

      

        // Обход всех битов

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

        {

            // Подсчитать количество элементов с установленным i-ым битом

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

            int k = 0;

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

            {

                if ((arr[j] & (1 << i))!=0)

                    k++;

            }

      

            // Есть k установленных битов, значит k (k-1) / 2 пары.

            // Каждая пара добавляет 2 ^ i к ответу. Следовательно,

            // мы добавляем «2 ^ i * [k * (k-1) / 2]» к ответу.

            ans += (1 << i) * (k * (k - 1)/2);

        }

        return ans;

    }

  

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

    public static void main(String args[])

    {

        int arr[] = {5, 10, 15};

        int n = arr.length;

        System.out.println(pairAndSum(arr, n));

    }

}

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

python3

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

  
# Возвращает значение "arr [0] & arr [1] +
# arr [0] & arr [2] + ... arr [i] & arr [j] +
# ..... arr [n-2] & arr [n-1] "

def pairAndSum(arr, n) :

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

  

    # Пройдите через все биты

    for i in range(0,32) :

          

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

        # Инициализировать счет

        k = 0

        for j in range(0,n) :

            if ( (arr[j] & (1 << i)) ) :

                k = k + 1

  

        # Есть k установленных битов, значит k (k-1) / 2 пары.

        # Каждая пара добавляет 2 ^ я к ответу. Следовательно,

        # мы добавляем «2 ^ i * [k * (k-1) / 2]» к ответу.

        ans = ans + (1 << i) * (k * (k - 1) // 2)

      

    return ans

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

arr = [5, 10, 15]

n = len(arr) 

print(pairAndSum(arr, n))

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

C #

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

using System;

  

class GFG {

      

    // Возвращает значение "arr [0] & arr [1] +

    // arr [0] & arr [2] + ... arr [i] & arr [j] +

    // ..... arr [n-2] & arr [n-1] "

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

    {

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

      

        // Обход всех битов

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

        {

            // Подсчитать количество элементов с

            // я установил бит

            int k = 0;

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

            {

                if ((arr[j] & (1 << i))!=0)

                    k++;

            }

      

            // Есть k установленных битов, значит

            // k (k-1) / 2 пары. Каждая пара

            // добавляет 2 ^ i к ответу.

            // Поэтому мы добавляем «2 ^ i *

            // [k * (k-1) / 2] "к ответу.

            ans += (1 << i) * (k * (k - 1)/2);

        }

          

        return ans;

    }

  

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

    public static void Main()

    {

        int []arr = new int[]{5, 10, 15};

        int n = arr.Length;

          

        Console.Write(pairAndSum(arr, n));

    }

}

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

PHP

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

  
// Возвращает значение "arr [0] &
// arr [1] + arr [0] & arr [2] +
// ... arr [i] & arr [j] + .....
// arr [n-2] & arr [n-1] "

function pairAndSum($arr, $n)

{

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

    $ans = 0; 

  

    // Обход всех битов

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

    {

          

        // Подсчитать количество элементов

        // с установленным битом

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

        $k = 0; 

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

            if (($arr[$j] & (1 << $i)) )

                $k++;

  

        // Есть k установленных битов,

        // означает k (k-1) / 2 пары.

        // Каждая пара добавляет 2 ^ i к

        // ответ. Следовательно,

        // мы добавляем "2 ^ i * [k * (k-1) / 2]"

        // к ответу.

        $ans += (1 << $i) * ($k * ($k - 1) / 2);

    }

  

    return $ans;

}

  

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

    $arr = array(5, 10, 15);

    $n = sizeof($arr);

    echo pairAndSum($arr, $n) ;

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


Выход:

15

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

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

Сумма побитовых и всех пар в данном массиве

0.00 (0%) 0 votes