Formatted question description: https://leetcode.ca/all/1814.html

1814. Count Nice Pairs in an Array

Level

Medium

Description

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

Return the number of nice pairs of indices. Since that number can be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [42,11,1,97]

Output: 2

Explanation: The two pairs are:

(0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
(1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.

Example 2:

Input: nums = [13,10,35,24,76]

Output: 4

Constraints:

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

Solution

If a pair of indices (i, j) (where i < j) is nice, then there is nums[i] + rev(nums[j]) == nums[j] + rev(nums[i]), which is equivalent to nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]). Therefore, for each 0 <= i < nums.length, calculate nums[i] - rev(nums[i]) and use an array differences to store the calculated differences. Then sort differences. For each difference, if there are k values, then the number of nice pairs with difference is k * (k - 1) / 2. Loop over differences to calculate the number of nice pairs.

class Solution {
    public int countNicePairs(int[] nums) {
        final int MODULO = 1000000007;
        int length = nums.length;
        int[] differences = new int[length];
        for (int i = 0; i < length; i++) {
            int reverseNum = reverse(nums[i]);
            differences[i] = nums[i] - reverseNum;
        }
        Arrays.sort(differences);
        long pairs = 0;
        int prev = differences[0];
        long consecutive = 1;
        for (int i = 1; i < length; i++) {
            int curr = differences[i];
            if (curr == prev)
                consecutive++;
            else {
                pairs = (pairs + consecutive * (consecutive - 1) / 2) % MODULO;
                prev = curr;
                consecutive = 1;
            }
        }
        pairs = (pairs + consecutive * (consecutive - 1) / 2) % MODULO;
        return (int) pairs;
    }

    public int reverse(int x) {
        int max = Integer.MAX_VALUE / 10, min = Integer.MIN_VALUE / 10;
        int reversed = 0;
        while (x != 0) {
            int lastDigit = x % 10;
            if (reversed > max || reversed == max && lastDigit > 7)
                return 0;
            if (reversed < min || reversed == min && lastDigit < -8)
                return 0;
            x /= 10;
            reversed = reversed * 10 + lastDigit;
        }
        return reversed;
    }
}

############

class Solution {
    public int countNicePairs(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            int y = x - rev(x);
            cnt.merge(y, 1, Integer::sum);
        }
        final int mod = (int) 1e9 + 7;
        long ans = 0;
        for (int v : cnt.values()) {
            ans = (ans + (long) v * (v - 1) / 2) % mod;
        }
        return (int) ans;
    }

    private int rev(int x) {
        int y = 0;
        for (; x > 0; x /= 10) {
            y = y * 10 + x % 10;
        }
        return y;
    }
}

// OJ: https://leetcode.com/problems/count-nice-pairs-in-an-array/
// Time: O(N)
// Space: O(N)
class Solution {
    long rev(long x) {
        long ans = 0;
        while (x) {
            ans = ans * 10 + x % 10;
            x /= 10;
        }
        return ans;
    }
public:
    int countNicePairs(vector<int>& A) {
        unordered_map<int, int> m;
        long ans = 0, mod = 1e9+7;
        for (int n : A) {
            long x = n - rev(n);
            ans = (ans + m[x]) % mod;
            m[x]++;
        }
        return ans;
    }
};

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def rev(x):
            y = 0
            while x:
                y = y * 10 + x % 10
                x //= 10
            return y

        cnt = Counter(x - rev(x) for x in nums)
        mod = 10**9 + 7
        return sum(v * (v - 1) // 2 for v in cnt.values()) % mod

############

# 1814. Count Nice Pairs in an Array
# https://leetcode.com/problems/count-nice-pairs-in-an-array/

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        count = Counter(num - int(str(num)[::-1]) for num in nums)
        
        return sum((c * (c-1) // 2) for c in count.values()) % (10 ** 9 + 7)

func countNicePairs(nums []int) (ans int) {
	rev := func(x int) (y int) {
		for ; x > 0; x /= 10 {
			y = y*10 + x%10
		}
		return
	}
	cnt := map[int]int{}
	for _, x := range nums {
		y := x - rev(x)
		cnt[y]++
	}
	const mod int = 1e9 + 7
	for _, v := range cnt {
		ans = (ans + v*(v-1)/2) % mod
	}
	return
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var countNicePairs = function (nums) {
    const rev = x => {
        let y = 0;
        for (; x > 0; x = Math.floor(x / 10)) {
            y = y * 10 + (x % 10);
        }
        return y;
    };
    const cnt = new Map();
    for (const x of nums) {
        const y = x - rev(x);
        cnt.set(y, (cnt.get(y) | 0) + 1);
    }
    let ans = 0;
    const mod = 1e9 + 7;
    for (const [_, v] of cnt) {
        ans = (ans + Math.floor((v * (v - 1)) / 2)) % mod;
    }
    return ans;
};

function countNicePairs(nums: number[]): number {
    const rev = (x: number): number => {
        let y = 0;
        while (x) {
            y = y * 10 + (x % 10);
            x = Math.floor(x / 10);
        }
        return y;
    };
    const mod = 10 ** 9 + 7;
    const cnt = new Map<number, number>();
    let ans = 0;
    for (const x of nums) {
        const y = x - rev(x);
        ans = (ans + (cnt.get(y) ?? 0)) % mod;
        cnt.set(y, (cnt.get(y) ?? 0) + 1);
    }
    return ans;
}

public class Solution {
    public int CountNicePairs(int[] nums) {
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        foreach (int x in nums) {
            int y = x - Rev(x);
            cnt[y] = cnt.GetValueOrDefault(y, 0) + 1;
        }
        int mod = (int)1e9 + 7;
        long ans = 0;
        foreach (int v in cnt.Values) {
            ans = (ans + (long)v * (v - 1) / 2) % mod;
        }
        return (int)ans;
    }

    private int Rev(int x) {
        int y = 0;
        while (x > 0) {
            y = y * 10 + x % 10;
            x /= 10;
        }
        return y;
    }
}

1814 - Count Nice Pairs in an Array

1814. Count Nice Pairs in an Array

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1814. Count Nice Pairs in an Array

Level

Description

Solution

All Problems

All Solutions