- Arrays, Bit Magic, Bitwise-AND, Combinatorial, Mathematical

Sum of Bitwise AND of all unordered triplets of an array

Sum of Bitwise AND of all unordered triplets of an arrayGiven an array arr[] consisting of N positive integers, the task is to find the sum of Bitwise AND of all possible triplets (arr[i], arr[j], arr[k]) such that i < j < k.Examples:Input: arr[] = {3, 5, 4, 7}Output: 5Explanation: Sum of Bitwise AND of all possible triplets = (3 & 5 & 4) + (3 & 5 & 7) + (3 & 4 & 7) + (5 & 4 & 7) = 0 + 1 + 0 + 4 = 5.Input: arr[] = {4, 4, 4}Output: 4Naive Approach: The simplest approach to solve the given problem is to generate all possible triplets (i, j, k) of the given array such that i < j < k  and print the sum of Bitwise AND of all possible triplets.Below is the implementation of the above approach:C++  #include using namespace std;  void tripletAndSum(int arr[], int n){            int ans = 0;              for (int i = 0; i < n; i++) {        for (int j = i + 1; j < n; j++) {            for (int k = j + 1; k < n; k++) {                                  ans += arr[i] & arr[j] & arr[k];            }        }    }          cout