Count Almost Equal Pairs I

Medium
1819.

Count Almost Equal Pairs I

Count Almost Equal Pairs I is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.

You are given an array nums of positive integers.

Two integers x and y are called almost equal if they can be made equal by doing the following at most once: pick one of the two numbers and swap any two of its digits. A swap may put a zero in front, and the leading zeros are then simply ignored (so 30 can become 03, which is 3).

Return the number of index pairs i < j such that nums[i] and nums[j] are almost equal.

Example 1

Input
nums = [3,12,30,17,21]
Output
2
Explanation
`3` and `30` (swap the digits of `30` to get `03 = 3`), and `12` and `21`.

Example 2

Input
nums = [1,1,1,1,1]
Output
10
Explanation
Every pair is already equal, and there are `5 * 4 / 2 = 10` pairs.

Example 3

Input
nums = [123,231]
Output
0
Explanation
Turning `123` into `231` moves all three digits — one swap is not enough.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countPairs = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Almost Equal Pairs I — Solution in Python, Java & C++

Count Almost Equal Pairs I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Almost Equal Pairs I is a medium coding problem on arrays, hash table and sorting, asked in Amazon interviews.

Problem statement

You are given an array nums of positive integers.

Two integers x and y are called almost equal if they can be made equal by doing the following at most once: pick one of the two numbers and swap any two of its digits. A swap may put a zero in front, and the leading zeros are then simply ignored (so 30 can become 03, which is 3).

Return the number of index pairs i < j such that nums[i] and nums[j] are almost equal.

Example 1

Input: nums = [3,12,30,17,21]
Output: 2
Explanation: `3` and `30` (swap the digits of `30` to get `03 = 3`), and `12` and `21`.

Example 2

Input: nums = [1,1,1,1,1]
Output: 10
Explanation: Every pair is already equal, and there are `5 * 4 / 2 = 10` pairs.

Example 3

Input: nums = [123,231]
Output: 0
Explanation: Turning `123` into `231` moves all three digits — one swap is not enough.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 10^6

Hints for Count Almost Equal Pairs I

  1. Hint 1

    With at most 100 numbers you can afford to test every pair; the question is how to test one pair quickly.

  2. Hint 2

    Pad the shorter number with leading zeros so both have the same number of digits, then compare them digit by digit.

  3. Hint 3

    The pair is almost equal when no digit differs, or exactly two positions differ and the two differing digits are crossed (a[i] == b[j] and a[j] == b[i]).

How to solve Count Almost Equal Pairs I

One swap changes exactly two digit positions of one number. So after lining the two numbers up digit by digit (padding the shorter with zeros, which is what a swap into the leading position produces), they must either already agree everywhere or disagree in exactly two positions holding the same two digits in crossed order.

Approach

  1. For every pair i < j, take x = nums[i] and y = nums[j].
  2. Walk both numbers from the last digit, x % 10 and y % 10, dividing by 10 until both are zero — a number that runs out first contributes zeros, exactly like padding.
  3. Record the positions where the digits differ; stop early once there are three of them.
  4. Count the pair if there were no differences, or exactly two differences (a1, b1) and (a2, b2) with a1 == b2 and a2 == b1.

Why it works

Swapping two digits of x changes it only in those two positions, and only by exchanging their values. So x can reach y in one swap precisely when they differ in two positions whose digits are crossed; swapping in y instead is the same condition read the other way. Leading zeros are harmless: x and y agree on every position beyond the longer length, and a swap that moves a zero to the front corresponds to padding the shorter number.

Complexity

  • Time — O(n^2 * d) with d ≤ 7 digits
  • Space — O(1)

Pitfalls

  • Comparing the decimal strings without padding misses pairs like 3 and 30.
  • Two differing positions are not enough on their own: 12 and 34 differ in two places but no swap helps.
  • Equal numbers count as almost equal — zero swaps is allowed.

Reference solution

Python

from typing import List

def countPairs(nums: List[int]) -> int:
    def almost_equal(x: int, y: int) -> bool:
        diff = []
        while x > 0 or y > 0:
            a, b = x % 10, y % 10
            if a != b:
                diff.append((a, b))
                if len(diff) > 2:
                    return False
            x //= 10
            y //= 10
        if not diff:
            return True
        return len(diff) == 2 and diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]

    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if almost_equal(nums[i], nums[j]):
                count += 1
    return count

Java

static boolean almostEqual(int x, int y) {
    int cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
    while (x > 0 || y > 0) {
        int a = x % 10, b = y % 10;
        if (a != b) {
            if (cnt == 0) { a1 = a; b1 = b; }
            else if (cnt == 1) { a2 = a; b2 = b; }
            cnt++;
            if (cnt > 2) return false;
        }
        x /= 10;
        y /= 10;
    }
    return cnt == 0 || (cnt == 2 && a1 == b2 && a2 == b1);
}

public static int countPairs(int[] nums) {
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (almostEqual(nums[i], nums[j])) count++;
        }
    }
    return count;
}

C++

bool almostEqual(int x, int y) {
    int cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
    while (x > 0 || y > 0) {
        int a = x % 10, b = y % 10;
        if (a != b) {
            if (cnt == 0) { a1 = a; b1 = b; }
            else if (cnt == 1) { a2 = a; b2 = b; }
            cnt++;
            if (cnt > 2) return false;
        }
        x /= 10;
        y /= 10;
    }
    return cnt == 0 || (cnt == 2 && a1 == b2 && a2 == b1);
}

int countPairs(vector<int>& nums) {
    int count = 0, n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (almostEqual(nums[i], nums[j])) count++;
        }
    }
    return count;
}

JavaScript

var countPairs = function(nums) {
    var count = 0;
    for (var i = 0; i < nums.length; i++) {
        for (var j = i + 1; j < nums.length; j++) {
            if (almostEqual(nums[i], nums[j])) count++;
        }
    }
    return count;
};

var almostEqual = function(x, y) {
    var cnt = 0, a1 = 0, b1 = 0, a2 = 0, b2 = 0;
    while (x > 0 || y > 0) {
        var a = x % 10, b = y % 10;
        if (a !== b) {
            if (cnt === 0) { a1 = a; b1 = b; }
            else if (cnt === 1) { a2 = a; b2 = b; }
            cnt++;
            if (cnt > 2) return false;
        }
        x = Math.floor(x / 10);
        y = Math.floor(y / 10);
    }
    return cnt === 0 || (cnt === 2 && a1 === b2 && a2 === b1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets