Counting Elements

Problem Statement

The goal is to analyze an integer array arr and determine how many elements x in the array have the characteristic that the element x + 1 is also present in the array. It's crucial to note that if there are duplicates of x in arr, each duplicate should be counted separately. This implies that every instance of an element that satisfies the condition should influence the final count independently of its duplicates.

Examples

Example 1

Input:

arr = [1,2,3]

Output:

2

Explanation:

1 and 2 are counted cause 2 and 3 are in arr.

Example 2

Input:

arr = [1,1,3,3,5,5,7,7]

Output:

0

Explanation:

No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.

Constraints

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

Approach and Intuition

The problem is straightforward where the task is to find the count of such elements x in the array arr that also have their consecutive number x + 1 present in the array. Here's how you can approach solving this problem:

1. Read the input array arr.
2. Create a structure to keep track of all elements in the array for quick lookup. The best fit would be a set since it allows O(1) average-time complexity for lookups and avoids counting the same element more than once.
3. Initialize a counter to zero. This will hold the count of elements meeting the condition.
4. Loop through each element x in the array:
   • For every element x, check if x + 1 exists in the set.
   • If x + 1 is found, increment the counter.
5. After iterating through the array, the counter will represent the total number of elements x such that both x and x + 1 are present.

Examples Revisited

To offer further intuition, let's revisit the provided examples considering the above approach:

• For Example 1, the array arr is [1,2,3]. Both 1 and 2 have their consecutive numbers 2 and 3, respectively, present in the array. Hence, the counter results in 2.

• In Example 2, the array is [1,1,3,3,5,5,7,7]. The consecutive elements after each number in the array, such as 2, 4, 6, and 8, are not present in the array. As a result, the counter remains 0.

This procedure ensures effective counting while maintaining a low time complexity, leveraging the properties of set data structures for fast element lookup.

Solutions

public int tallyRepetitiveElements(int[] data) {
    Arrays.sort(data);
    int tally = 0;
    int sequenceLength = 1;
    for (int index = 1; index < data.length; index++) {
        if (data[index - 1] != data[index]) {
            if (data[index - 1] + 1 == data[index]) {
                tally += sequenceLength;
            }
            sequenceLength = 0;
        }
        sequenceLength++;
    }
    return tally;
}