Count OR Pairs in Java

Programmers often have to count the number of pairs with logical OR operations. To find the number of pairs whose logical OR value exceeds or equals a given integer value from an array of integers, we need to take an array of integers and divide it by a logical OR value

Example 1:

Input: [10,20,30,40,50]

orValue: 15

Explanation: The variety of OR pairs in the array that have a value greater than or identical to 15 is 10. Each detail within the array is paired with all of the factors that come after it ensuing in 10 OR pairs.

Approach: Using Brute Force

ALGORITHM:

Step 1: Start the main function.

Step 2: Define the countORPairs function that takes an array arr and an integer orValue as parameters. This function will return the count of OR pairs.

Step 3: Initialize the count variable to 0, which will keep track of the count of OR pairs.

Step 4: Get the length of the array arr and keep it in the variable n.

Step 5: Start a loop from i = 0 to n - 1 to iterate over every detail inside the array.

Step 6: Inside the outer loop, start a nested loop from j = i 1 to n - 1 to evaluate with all next elements.

Step 7: Perform a bitwise OR operation on the pair of factors arr[i] and arr[j] and save the bring about the variable end result.

Step 8: Check if the result is greater than or equal to the orValue. If true, increment the count variable by 1.

Step 9: Repeat steps 6 to 8 until all pairs have been compared.

Step 10: Return the final value of count.

Step 11: End the countORPairs function.

Step 12: In the main function, initialize arrays arr4 with the given values, and define the respective orValue for each example.

Step 13: Call the countORPairs function for each example with the corresponding arrays and orValue.

Step 14: Print the result for each example.

Step 15: End the main function.

FileName: ORPairsCount.java

import java.util.*;
public class ORPairsCount
{
 // Function to count the number of OR pairs
 public static int countORPairs(int[] arr, int orValue) {
 int count = 0;
 int n=arr.length;
 // Iterate over each element in the array
 for (int i=0;i<n;i++)
 {
 // Compare with all subsequent elements
 for (int j=i+1;j<n;j++)
 {
 // Perform bitwise OR operation on the pair of elements
 int result=arr[i]|arr[j];
 if (result>=orValue)
 {
 count++;
 }
 }
 }
 return count;
 }
 public static void main(String[] args)
 {
 int[] arr4={10,20,30,40,50};
 int orValue4 = 15;
 int count4 = countORPairs(arr4, orValue4);
 System.out.println("Example 1: Number of OR pairs greater than or equal to "+orValue4+" is "+count4);
 }
}

Output:

Example 1: Number of OR pairs greater than or equal to 15 is 10

Complexity Analysis:

Time Complexity:

The time complexity of this brute force approach is O(n^2), where n is the size of the input array.

Space Complexity:

The space complexity of this approach is O(1), as we only use a constant amount of additional space to store the variables count, n, i, j, and result. The input array is not modified, and no extra space is used that depends on the input size.

Implementation: Using Mathematical Approach

ALGORITHM:

Step 1: Start by defining the CountORPairs class.

Step 2: Implement the countORPairs method that takes an input array, its size, and the OR value as parameters.

Step 3: Initialize countPairs and countGreater variables to keep track of the counts.

Step 4: Traverse the input array using a loop.

Step 5: For each element, check if it is greater than the OR value.

Step 6: If it is greater, increment countGreater.

Step 7: For each element greater than the OR value, there are (size - countGreater) remaining elements that can form OR pairs.

Step 8: Add this count to countPairs.

Step 9: After traversing the array, return the value of countPairs.

Step 10: In the main method, create an instance of CountORPairs and call the countORPairs method with the appropriate input parameters.

Step 11: Print the result.

FileName: CountORPairs.java

import java.util.*;
public class CountORPairs {
 // Function to count the number of OR pairs
 public int countORPairs(int[] inputArr, int size, int orValue) {
 int countPairs = 0;
 int countGreater = 0;
 // Traverse the input array
 for (int j= 0;j<size;j++) {
 // Count the number of elements greater than orValue
 if (inputArr[j] > orValue) {
 countGreater++;
 // For each element greater than orValue, count the remaining elements as OR pairs
 countPairs += (size - countGreater);
 }
 }
 return countPairs;
 }
 public static void main(String[] args) {
 CountORPairs obj = new CountORPairs();
 int[] arr2 = {10, 20, 30, 40, 50};
 int orValue2 = 15;
 int size2 = arr2.length;
 int count2 = obj.countORPairs(arr2, size2, orValue2);
 System.out.println("Example 1: Number of OR pairs greater than " + orValue2 + " is " + count2);
 }
}

Output:

Example 1: Number of OR pairs greater than 15 is 10

Complexity Analysis:

Time complexity:

The time complexity of the mathematical approach is O(n), where n is the size of the input array.

Space complexity:

The space complexity is O(1) because we use a constant amount of extra space to store the counts and variables.