Given an array arr[] consisting of N powers of 2, the task is to count the number of pairs (arr[i], arr[j]) such that i < j and arr[j] is divisible by arr[i].
Examples:
Input: arr[] = {4, 16, 8, 64}
Output: 5
Explanation:
The pairs satisfying the given condition are {4, 16}, {4, 8}, {4, 64}, {16, 64}, {8, 64}.Input: arr[] = {2, 4, 8, 16}
Output: 6
Explanation:
The pairs satisfying the given condition are {2, 4}, {2, 8}, {2, 16}, {4, 8}, {4, 16}, {8, 16}.
Naive Approach: The simplest approach is to generate all pairs of the given array arr[] and for each pair, check if arr[j] % arr[i] is 0 or not. If found to be true, increment count by 1. Finally, print the value of count after checking for all pairs.
C++
#include <iostream>#include <vector>using namespace std;int countPairs(vector<int> arr) { int count = 0; for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++) { if (arr[j] % arr[i] == 0 && (arr[j] & (arr[j]-1)) == 0) { count++; } } } return count;}int main() { vector<int> arr = {4, 16, 8, 64}; cout << countPairs(arr) << endl; // Output: 5 vector<int> arr2 = {2, 4, 8, 16}; cout << countPairs(arr2) << endl; // Output: 6 return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { // Function to count pairs in the given list static int countPairs(List<Integer> arr) { int count = 0; // Iterate through the elements in the list for (int i = 0; i < arr.size(); i++) { for (int j = i+1; j < arr.size(); j++) { // Check if arr[j] is divisible by arr[i] and arr[j] is a power of 2 if (arr.get(j) % arr.get(i) == 0 && (arr.get(j) & (arr.get(j) - 1)) == 0) { count++; } } } return count; } public static void main(String[] args) { // Create a list of integers List<Integer> arr = new ArrayList<>(); arr.add(4); arr.add(16); arr.add(8); arr.add(64); // Count and print the pairs that meet the criteria System.out.println(countPairs(arr)); // Output: 5 // Create another list of integers List<Integer> arr2 = new ArrayList<>(); arr2.add(2); arr2.add(4); arr2.add(8); arr2.add(16); // Count and print the pairs that meet the criteria System.out.println(countPairs(arr2)); // Output: 6 }} |
Python
def count_pairs(arr): count = 0 for i in range(len(arr)): for j in range(i+1, len(arr)): if arr[j] % arr[i] == 0 and (arr[j] & (arr[j]-1)) == 0: count += 1 return countarr = [4, 16, 8, 64]print(count_pairs(arr)) # Output: 5arr = [2, 4, 8, 16]print(count_pairs(arr)) # Output: 6 |
C#
using System;using System.Collections.Generic;class Program { static int CountPairs(List<int> arr) { int count = 0; for (int i = 0; i < arr.Count; i++) { for (int j = i+1; j < arr.Count; j++) { if (arr[j] % arr[i] == 0 && (arr[j] & (arr[j]-1)) == 0) { count++; } } } return count; } static void Main(string[] args) { List<int> arr = new List<int> {4, 16, 8, 64}; Console.WriteLine(CountPairs(arr)); // Output: 5 List<int> arr2 = new List<int> {2, 4, 8, 16}; Console.WriteLine(CountPairs(arr2)); // Output: 6 }} |
Javascript
function countPairs(arr) { let count = 0; for (let i = 0; i < arr.length; i++) { for (let j = i + 1; j < arr.length; j++) { if (arr[j] % arr[i] === 0 && (arr[j] & (arr[j] - 1)) === 0) { count++; } } } return count;}const arr1 = [4, 16, 8, 64];console.log(countPairs(arr1)); // Output: 5const arr2 = [2, 4, 8, 16];console.log(countPairs(arr2)); // Output: 6 |
Output
5 6
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the observation that any power of 2 has only one set bit in its binary representation. For any such element arr[j], all the powers of 2 which have their set bits at a position less than or equal to the position of a set bit of arr[j], will satisfy the given condition. Follow the steps below to solve the problem:
- Initialize an auxiliary array setBits of size equal to 31, and initialize count as 0 to store the number of required pairs.
- Traverse the array arr[] using the variable i and perform the following operations:
- Store the leftmost set bit of arr[i] in bitPos.
- Iterate in the range[0, bitPos] using the variable j and increment count by setBits[j] in each step.
- Increment setBits[bitPos] by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// pairs as per the given conditionsvoid numberOfPairs(int arr[], int N){ // Initialize array set_bits as 0 int set_bits[31] = { 0 }; // Store the total number of // required pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Store arr[i] in x int x = arr[i]; // Store the position of the // leftmost set bit in arr[i] int bitpos = -1; while (x > 0) { // Increase bit position bitpos++; // Divide by 2 to shift bits // in right at each step x /= 2; } // Count of pairs for index i // till its set bit position for (int j = 0; j <= bitpos; j++) { count += set_bits[j]; } // Increasing count of set bit // position of current element set_bits[bitpos]++; } // Print the answer cout << count;}// Driver Codeint main(){ int arr[] = { 4, 16, 8, 64 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call numberOfPairs(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the number of// pairs as per the given conditionsstatic void numberOfPairs(int arr[], int N){ // Initialize array set_bits as 0 int []set_bits = new int[31]; Arrays.fill(set_bits, 0); // Store the total number of // required pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Store arr[i] in x int x = arr[i]; // Store the position of the // leftmost set bit in arr[i] int bitpos = -1; while (x > 0) { // Increase bit position bitpos++; // Divide by 2 to shift bits // in right at each step x /= 2; } // Count of pairs for index i // till its set bit position for (int j = 0; j <= bitpos; j++) { count += set_bits[j]; } // Increasing count of set bit // position of current element set_bits[bitpos]++; } // Print the answer System.out.println(count);}// Driver Codepublic static void main(String args[]){ int arr[] = { 4, 16, 8, 64 }; int N = arr.length; // Function Call numberOfPairs(arr, N);}}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python3 program for the above approach# Function to count the number of# pairs as per the given conditionsdef numberOfPairs(arr, N): # Initialize array set_bits as 0 set_bits = [0]*31 # Store the total number of # required pairs count = 0 # Traverse the array arr[] for i in range(N): # Store arr[i] in x x = arr[i] # Store the position of the # leftmost set bit in arr[i] bitpos = -1 while (x > 0): # Increase bit position bitpos += 1 # Divide by 2 to shift bits # in right at each step x //= 2 # Count of pairs for index i # till its set bit position for j in range(bitpos + 1): count += set_bits[j] # Increasing count of set bit # position of current element set_bits[bitpos] += 1 # Print the answer print (count)# Driver Codeif __name__ == '__main__': arr = [4, 16, 8, 64] N = len(arr) # Function Call numberOfPairs(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG{// Function to count the number of// pairs as per the given conditionsstatic void numberOfPairs(int[] arr, int N){ // Initialize array set_bits as 0 int []set_bits = new int[31]; for (int i = 0; i < N; i++) { set_bits[i] = 0; } // Store the total number of // required pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Store arr[i] in x int x = arr[i]; // Store the position of the // leftmost set bit in arr[i] int bitpos = -1; while (x > 0) { // Increase bit position bitpos++; // Divide by 2 to shift bits // in right at each step x /= 2; } // Count of pairs for index i // till its set bit position for (int j = 0; j <= bitpos; j++) { count += set_bits[j]; } // Increasing count of set bit // position of current element set_bits[bitpos]++; } // Print the answer Console.Write(count);}// Driver Codestatic public void Main(){ int[] arr = { 4, 16, 8, 64 }; int N = arr.Length; // Function Call numberOfPairs(arr, N);}}// This code is contributed by splevel62. |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// pairs as per the given conditionsfunction numberOfPairs(arr, N){ // Initialize array set_bits as 0 let set_bits = []; for (let i = 0; i < 31; i++) { set_bits[i] = 0; } // Store the total number of // required pairs let count = 0; // Traverse the array arr[] for (let i = 0; i < N; i++) { // Store arr[i] in x let x = arr[i]; // Store the position of the // leftmost set bit in arr[i] let bitpos = -1; while (x > 0) { // Increase bit position bitpos++; // Divide by 2 to shift bits // in right at each step x = Math.floor( x / 2 ); } // Count of pairs for index i // till its set bit position for (let j = 0; j <= bitpos; j++) { count += set_bits[j]; } // Increasing count of set bit // position of current element set_bits[bitpos]++; } // Print the answer document.write(count);}// Driver Code let arr = [ 4, 16, 8, 64 ]; let N = arr.length; // Function Call numberOfPairs(arr, N); </script> |
Output
5
Time Complexity: O(N*log M), where M is the largest element in the array.
Auxiliary Space: O(1)
Share your thoughts in the comments
