Welcome to Subscribe On Youtube

1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers

Description

Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:

  • Type 1: Triplet (i, j, k) if nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.
  • Type 2: Triplet (i, j, k) if nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.

 

Example 1:

Input: nums1 = [7,4], nums2 = [5,2,8,9]
Output: 1
Explanation: Type 1: (1, 1, 2), nums1[1]2 = nums2[1] * nums2[2]. (42 = 2 * 8).

Example 2:

Input: nums1 = [1,1], nums2 = [1,1,1]
Output: 9
Explanation: All Triplets are valid, because 12 = 1 * 1.
Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2).  nums1[i]2 = nums2[j] * nums2[k].
Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]2 = nums1[j] * nums1[k].

Example 3:

Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]
Output: 2
Explanation: There are 2 valid triplets.
Type 1: (3,0,2).  nums1[3]2 = nums2[0] * nums2[2].
Type 2: (3,0,1).  nums2[3]2 = nums1[0] * nums1[1].

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 1 <= nums1[i], nums2[i] <= 105

Solutions

  • class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();
        for (int v : nums1) {
            cnt1.put(v, cnt1.getOrDefault(v, 0) + 1);
        }
        for (int v : nums2) {
            cnt2.put(v, cnt2.getOrDefault(v, 0) + 1);
        }
        long ans = 0;
        for (var e1 : cnt1.entrySet()) {
            long a = e1.getKey(), x = e1.getValue();
            for (var e2 : cnt2.entrySet()) {
                long b = e2.getKey(), y = e2.getValue();
                if ((a * a) % b == 0) {
                    long c = a * a / b;
                    if (b == c) {
                        ans += x * y * (y - 1);
                    } else {
                        ans += x * y * cnt2.getOrDefault((int) c, 0);
                    }
                }
                if ((b * b) % a == 0) {
                    long c = b * b / a;
                    if (a == c) {
                        ans += x * (x - 1) * y;
                    } else {
                        ans += x * y * cnt1.getOrDefault((int) c, 0);
                    }
                }
            }
        }
        return (int) (ans >> 1);
    }
}

  • class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        cnt1 = Counter(nums1)
        cnt2 = Counter(nums2)
        ans = 0
        for a, x in cnt1.items():
            for b, y in cnt2.items():
                if a * a % b == 0:
                    c = a * a // b
                    if b == c:
                        ans += x * y * (y - 1)
                    else:
                        ans += x * y * cnt2[c]
                if b * b % a == 0:
                    c = b * b // a
                    if a == c:
                        ans += x * (x - 1) * y
                    else:
                        ans += x * y * cnt1[c]
        return ans >> 1


  • func numTriplets(nums1 []int, nums2 []int) (ans int) {
	cnt1 := map[int]int{}
	cnt2 := map[int]int{}
	for _, v := range nums1 {
		cnt1[v]++
	}
	for _, v := range nums2 {
		cnt2[v]++
	}
	for a, x := range cnt1 {
		for b, y := range cnt2 {
			if a*a%b == 0 {
				c := a * a / b
				if b == c {
					ans += x * y * (y - 1)
				} else {
					ans += x * y * cnt2[c]
				}
			}
			if b*b%a == 0 {
				c := b * b / a
				if a == c {
					ans += x * (x - 1) * y
				} else {
					ans += x * y * cnt1[c]
				}
			}
		}
	}
	ans /= 2
	return
}

  • class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        auto cnt1 = count(nums1);
        auto cnt2 = count(nums2);
        return cal(cnt1, nums2) + cal(cnt2, nums1);
    }

    unordered_map<long long, int> count(vector<int>& nums) {
        unordered_map<long long, int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                cnt[(long long) nums[i] * nums[j]]++;
            }
        }
        return cnt;
    }

    int cal(unordered_map<long long, int>& cnt, vector<int>& nums) {
        int ans = 0;
        for (int x : nums) {
            ans += cnt[(long long) x * x];
        }
        return ans;
    }
};


  • function numTriplets(nums1: number[], nums2: number[]): number {
    const cnt1 = count(nums1);
    const cnt2 = count(nums2);
    return cal(cnt1, nums2) + cal(cnt2, nums1);
}

function count(nums: number[]): Map<number, number> {
    const cnt: Map<number, number> = new Map();
    for (let j = 0; j < nums.length; ++j) {
        for (let k = j + 1; k < nums.length; ++k) {
            const x = nums[j] * nums[k];
            cnt.set(x, (cnt.get(x) || 0) + 1);
        }
    }
    return cnt;
}

function cal(cnt: Map<number, number>, nums: number[]): number {
    return nums.reduce((acc, x) => acc + (cnt.get(x * x) || 0), 0);
}

All Problems

All Solutions