Given a binary array arr[] of size N, the task is to print the sum of product of all pairs of the given array elements.
Note: The binary array contains only 0 and 1.
Examples:
Input: arr[] = {0, 1, 1, 0, 1}
Output: 3
Explanation: Sum of product of all possible pairs are: {0 × 1 + 0 × 1 + 0 × 0 + 0 × 1 + 1 × 1 + 1 × 0 + 1 × 1 + 1 × 0 + 1 × 1 + 0 × 1}.
Therefore, the required output is 3.Input: arr[] = {1, 1, 1, 1}
Output: 6
Naive Approach: The simplest approach to solve the problem is to use generate all possible pairs from the array and calculate the sum of their product.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, consider only those pairs in which both the elements are 1. Following are the observations:
If there is a pair (arr[i], arr[j]) where arr[i] × arr[j] = 1, then arr[i] and arr[j] must be 1.
Total number of pairs that satisfy (arr[i] × arr[j] = 1) are:
=>
=> cntOne × (cntOne – 1) / 2
where, cntOne is the count of 1s in the given array
Follow the steps below to solve the problem:
- Initialize the variable cntOne to store the count of 1s from the given array.
- Finally, return the value of cntOne * (cntOne – 1) / 2.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std;// Function to print the sum of product// of all pairs of the given arrayint productSum(int arr[], int N){ // Stores count of one in // the given array int cntOne = 0; for(int i = 0; i < N; i++) { // If current element is 1 if (arr[i] == 1) // Increase count cntOne++; } // Return the sum of product // of all pairs return cntOne * (cntOne - 1) / 2;} // Driver Codeint main(){ int arr[] = { 0, 1, 1, 0, 1 }; // Stores the size of // the given array int n = sizeof(arr) / sizeof(arr[0]); cout << productSum(arr, n) << endl;}// This code is contributed by code_hunt |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to print the sum of product // of all pairs of the given array static int productSum(int[] arr) { // Stores count of one in // the given array int cntOne = 0; // Stores the size of // the given array int N = arr.length; for (int i = 0; i < N; i++) { // If current element is 1 if (arr[i] == 1) // Increase count cntOne++; } // Return the sum of product // of all pairs return cntOne * (cntOne - 1) / 2; } // Driver Code public static void main(String[] args) { int[] arr = { 0, 1, 1, 0, 1 }; System.out.println(productSum(arr)); }} |
Python3
# Python3 program to implement # the above approach # Function to print the sum of product# of all pairs of the given arraydef productSum(arr): # Stores count of one in # the given array cntOne = 0 # Stores the size of # the given array N = len(arr) for i in range(N): # If current element is 1 if (arr[i] == 1): # Increase count cntOne += 1 # Return the sum of product # of all pairs return cntOne * (cntOne - 1) // 2# Driver Codearr = [ 0, 1, 1, 0, 1 ]print(productSum(arr))# This code is contributed by code_hunt |
C#
// C# program to implement // the above approach using System;class GFG{ // Function to print the sum of product// of all pairs of the given arraystatic int productSum(int[] arr){ // Stores count of one in // the given array int cntOne = 0; // Stores the size of // the given array int N = arr.Length; for(int i = 0; i < N; i++) { // If current element is 1 if (arr[i] == 1) // Increase count cntOne++; } // Return the sum of product // of all pairs return cntOne * (cntOne - 1) / 2;}// Driver Codepublic static void Main(){ int[] arr = { 0, 1, 1, 0, 1 }; Console.Write(productSum(arr));}}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approach// Function to print the sum of product// of all pairs of the given arrayfunction productSum(arr, N){ // Stores count of one in // the given array let cntOne = 0; for(let i = 0; i < N; i++) { // If current element is 1 if (arr[i] == 1) // Increase count cntOne++; } // Return the sum of product // of all pairs return cntOne * (cntOne - 1) / 2;}// Driver Code let arr = [ 0, 1, 1, 0, 1 ]; // Stores the size of // the given array let n = arr.length; document.write(productSum(arr, n) + "<br>");// This code is contributed by Mayank Tyagi</script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
