We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Counting Elements

Number: 1391

Difficulty: Easy

Paid? Yes

Companies: DRW

Problem Description

Given an integer array arr, count how many elements x there are such that x + 1 is also present in arr. Duplicates in arr are counted separately.

Key Insights

  • Use a hash table or set to store unique elements from arr for constant time lookups.
  • Iterate through each element in arr and check if x + 1 exists in the set.
  • Count each valid occurrence, including duplicates.
  • This approach efficiently handles the problem without needing nested loops.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in arr (set lookups are O(1) on average).
Space Complexity: O(n), due to the use of an auxiliary set to store unique elements.

Solution

The solution leverages a set to achieve constant time membership checks. First, we convert arr to a set of unique numbers. Then, iterate through arr, and for each element, check if (element + 1) exists in the set. If it does, increment the count. This approach correctly handles duplicates by counting each occurrence during iteration.

Code Solutions

# Function to count elements where (x + 1) is in the array
def count_elements(arr):
    # Create a set of unique numbers for O(1) lookups
    unique_numbers = set(arr)
    count = 0
    # Iterate through each number in the array
    for number in arr:
        # If (number + 1) exists in the unique set, increment count
        if number + 1 in unique_numbers:
            count += 1
    return count

# Example usage:
# arr = [1, 2, 3]
# print(count_elements(arr))  # Expected output: 2
← Back to All Questions