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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Almost Equal Pairs I

Number: 3534

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array of positive integers, count the number of pairs (i, j) with i < j such that the two numbers are "almost equal." Two integers are considered almost equal if, by performing at most one swap of any two digits in one of the numbers, they can be transformed to be equal. Leading zeros after the swap are allowed.

Key Insights

  • For each number, generate all possible values after performing at most one swap (including keeping the number unchanged).
  • Compare each pair (i, j) by checking if there is an intersection between the sets of possible transformed values for the two numbers.
  • The maximum number of digits is small (since nums[i] <= 10^6), making it efficient to compute all swap outcomes.
  • Use a brute-force pairwise comparison as the array length is limited (n <= 100).

Space and Time Complexity

Time Complexity: O(n^2 * d^2) where n is the number of numbers and d is the number of digits (d is small, at most 7).
Space Complexity: O(n * m) where m is the number of unique outcomes for each number (m is limited by d^2).

Solution

We approach the problem by precomputing a set of possible numbers for each integer after performing at most one digit-swap (including the original number in the set). For every pair (i, j), we check if the two sets have any common element, meaning one number in one set equals one number in the other set, making them "almost equal." Due to small input sizes, iterating with nested loops and using set intersection is efficient.

Data structures used:

  • A list to store the generated sets for each number.
  • A set for each number to avoid duplicate values from swaps.

Algorithm steps:

  1. Convert the number to its string representation to access individual digits.
  2. Generate the candidate set by swapping every pair of digits (only if the swap produces a new configuration) while also including the original number.
  3. Iterate through all pairs (i, j) and check set intersections.
  4. Count pairs that share a common element.

Code Solutions

# Python solution for counting almost equal pairs
def countAlmostEqualPairs(nums):
    # Function to generate all possible numbers from at most one swap operation
    def generate_candidates(num):
        s = list(str(num))
        n = len(s)
        candidates = set()
        # Include the original number (no swap)
        candidates.add(int("".join(s)))
        # Try every pair of indices to swap
        for i in range(n):
            for j in range(i + 1, n):
                s[i], s[j] = s[j], s[i]  # swap the two digits
                candidates.add(int("".join(s)))
                s[i], s[j] = s[j], s[i]  # swap back to original
        return candidates

    # Precompute candidate sets for all numbers in the array
    candidates_list = [generate_candidates(num) for num in nums]
    count = 0
    n = len(nums)
    # Compare every pair (i, j) where i < j
    for i in range(n):
        for j in range(i+1, n):
            # If candidate sets have common element, increment counter
            if candidates_list[i] & candidates_list[j]:
                count += 1
    return count

# Example usage:
nums = [3, 12, 30, 17, 21]
print(countAlmostEqualPairs(nums))  # Expected output: 2
← Back to All Questions