# Number of Pairs Satisfying Inequality in Java

In this tutorial, we will learn about **number of pairs satisfying inequality in Java**. Counting pairs of elements in an array or collection that match a condition specified by an inequality is commonly referred to as the "number of pairs satisfying an inequality". Counting the number of pairs in an array (or two arrays) that satisfy a certain inequality can be approached in a basic way by looking at all possible pairings and determining whether they match the given condition.

**Examples:**

**Example 1:**

**Input:** nums1 = [3,2,5], nums2 = [2,2,1], diff = 1

**Output:** 3

**Explanation:**

Three sets of objects meet the required criteria:

- 3 - 2 <= 2 - 2 + 1 for i = 0 and j = 1. Given that 1 <= 1 and i < j, this pair meets the requirements.
- 3 - 5 <= 2 - 1 + 1 for i = 0 and j = 2. These requirements are met by this combination because i < j and -2 <= 2.
- If i = 1 and j = 2, then 2 - 5 <= 2 - 1 + 1. These requirements are met by this combination because i < j and -3 <= 2.

Therefore, we return 3.

**Example 2:**

**Input:** nums1 = [3,-1], nums2 = [-2,2], diff = -1

**Output:** 0

**Explanation:**

Since there does not exist any pair that satisfies the conditions, we return 0.

## Approach: Using binary indexed tree

### ALGORITHM:

**Step 1: **Make a Binary Indexed Tree called tree, with a size large enough to accommodate every possible value after normalization (to account for negative integers).**Step 2: **Accommodate negative values, a fixed number is added to each index. BIT does not allow for negative indices, this adjusts the index range to accommodate query and update operations with negative values.

**Step 3: **Determine the difference, v = a - b, for each element an in nums1 and b in nums2. Next, add v to the BIT (tree) so that this value is effectively counted.

**Step 4: **Find the count of all values in the BIT that are less than or equal to v + diff, the query will use the identical values, a and b. This is so that nums1[i] - nums1[j] <= nums2[i] - nums2[j] + diff, the all-time previous indices i that we are searching for.

**Step 5: **Return the count of valid i indices that precede the current index j of the query method. In order to meet our pairs requirement. For each j, this count is added to our response answer.

**Step 6: **Determine, the least significant bit that has been set to for a given number x. The BinaryIndexedTree class has a static function called lowbit. This function aids in navigating to parent or child nodes during update and query operations within the bidirectional update table (BIT).**Filename: PairInequality.java**

public class PairInequality

{

public static void main(String[] args)

{

// Given array

int[] array = {1, 2, 3, 4, 5,6};

int[] bit = new int[array.length + 1];

// initialize the count

int count = 0;

for (int i = 0; i<array.length; i++) {

update(bit, array[i], 1);

count += query(bit, array[i] - 1);

}

System.out.println("Number of pairs satisfying the inequality: " + count);

}

private static void update(int[] bit, int index, int value)

{

for (; index <bit.length; index += index & -index)

{

bit[index] += value;

}

}

private static int query(int[] bit, int index) {

int sum = 0;

for (; index > 0; index -= index & -index)

{

sum += bit[index];

}

return sum;

}

}

**Output:**

Number of pairs satisfying the inequality: 15

**Time complexity: **The time complexity of the program is O( nlogn), where n is the number of elements in the given array.

**Space complexity: **The space complexity of the program is O(n), where n is the number of elements in the given array.