Vultr DocsLatest Content

Counting Elements

Updated on 09 May, 2025
Counting Elements header image

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

  • Java
  • Python
java 
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;
}

The given Java code defines a method tallyRepetitiveElements that computes the tally of elements followed directly by the next consecutive integer in a sorted array. Here's a breakdown of the code:

  • Begin by sorting the input array using Arrays.sort(data).
  • Initialize two variables: tally to track the count of elements meeting the criteria, and sequenceLength to handle the length of consecutive runs.
  • Iterate through the array starting from the second element to compare with its predecessor.
  • Check conditions:
    • If the current element is different from the previous one (data[index - 1] != data[index]), then check if the previous element and current element are consecutive numbers (data[index - 1] + 1 == data[index]). If true, add the sequence length to the tally.
    • Reset sequenceLength if elements are not the same.
    • Increment sequenceLength after each iteration for assessing the next potential sequence.
  • Return the tally which includes the count of elements immediately followed by their consecutive integer in the array.

By following this approach, you effectively analyze and count sequences of consecutive numbers in an array.

python 
def tallyElements(self, nums: List[int]) -> int:
    nums.sort()
    tally = 0
    sequence_len = 1
    for index in range(len(nums)):
        if nums[index - 1] != nums[index]:
            if nums[index - 1] + 1 == nums[index]:
                tally += sequence_len
            sequence_len = 0
        sequence_len += 1
    return tally

This Python function tallyElements calculates the count of elements that have a next consecutive number in a given list nums. The approach involves sorting the list initially, which helps in linearly checking consecutive elements. Here's how the function operates:

  • Firstly, sort the nums list. This ensures that all consecutive numbers are adjacent, facilitating easier counting.
  • Initialize tally to store the number of valid elements and sequence_len to count consecutive duplicates.
  • Iterate through each element in the list nums starting from the first index. Use a for loop that iterates based on the index of list elements.
  • Inside the loop, check if the current element and the previous element are consecutive (i.e., the difference between them is exactly 1). If they are, increment the tally by sequence_len which counts the current sequence of consecutive duplicates.
  • Reset sequence_len to zero when the current and previous elements are not the same, ensuring that the next sequence count starts anew.
  • Finally, return tally as the output of the function.

The returned integer represents the number of elements in the list which are immediately followed by their consecutive number. This function effectively leverages sorting and linear traversal to solve the problem efficiently.

Comments

No comments yet.