Sum of Bitwise And of all pairs in a given array - GeeksforGeeks



Sum of Bitwise And of all pairs in a given array - GeeksforGeeks

Sum of Bitwise And of all pairs in a given array

Given an array "arr[0..n-1]" of integers, calculate sum of "arr[i] & arr[j]" for all the pairs in the given where i < j. Here & is bitwise AND operator. Expected time complexity is O(n).
Examples:

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: 9  Required Value = (1 & 2) + (1 & 3) + (1 & 4) +                    (2 & 3) + (2 & 4) + (3 & 4)                  = 0 + 1 + 0 + 2 + 0 + 0                 = 3  

We strongly recommend you to minimize your browser and try this yourself first.

A Brute Force approach is to run two loops and time complexity is O(n2).

// A Simple C++ program to compute sum of bitwise AND
// of all pairs
#include <bits/stdc++.h>
using namespace std;
 
// Returns value of "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;  // Initialize result
 
    // Consider all pairs (arr[i], arr[j) such that
    // i < j
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++)
           ans += arr[i] & arr[j];
 
    return ans;
}
 
// Driver program to test above function
int main()
{
    int arr[] = {5, 10, 15};
    int n = sizeof(arr) / sizeof (arr[0]);
    cout << pairAndSum(arr, n) << endl;
    return 0;
}

Output:

15

An Efficient Solution can solve this problem in O(n) time. The assumption here is that integers are represented using 32 bits.

The idea is to count number of set bits at every i'th position (i>=0 && i<=31). Any i'th bit of the AND of two numbers is 1 iff the corresponding bit in both the numbers is equal to 1. Let k be the count of set bits at i'th position. Total number of pairs with i'th set bit would be kC2 = k*(k-1)/2 (Count k means there are k numbers which have i'th set bit). Every such pair adds 2i to total sum. Similarly, we work for all other places and add the sum to our final answer.


Read full article from Sum of Bitwise And of all pairs in a given array - GeeksforGeeks


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts