Number of Ways Where Square of Number Is Equal to Product of Two Numbers - Problem

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]² == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.

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

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [7,4], nums2 = [5,2,8,9]

› Output: 1

💡 Note: Type 1: 7² = 49, but no pairs in nums2 multiply to 49. 4² = 16, but no pairs multiply to 16. Type 2: 5² = 25, no pairs in nums1 multiply to 25. 2² = 4, no pairs multiply to 4. 8² = 64, 7×9=63≠64. 9² = 81, no pairs multiply to 81. Wait, let me recalculate: 4² = 16, and 2×8 = 16, so we have triplet (1,1,2). Total = 1.

Example 2 — Multiple Matches

$ Input: nums1 = [1,1], nums2 = [1,1,1]

› Output: 9

💡 Note: Type 1: 1² = 1. Pairs in nums2 that multiply to 1: (0,1), (0,2), (1,2) = 3 pairs. Each nums1 element (2 total) can form triplets: 2×3 = 6. Type 2: 1² = 1. Pairs in nums1 that multiply to 1: (0,1) = 1 pair. Each nums2 element (3 total): 3×1 = 3. Total = 6 + 3 = 9.

Example 3 — No Matches

$ Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7]

› Output: 2

💡 Note: Type 1: 7² = 49, 7×7 = 49 ✓ (but 7 appears once in nums2). 8² = 64, no valid pairs. 3² = 9, 1×9 = 9 ✓. Type 2: Check each nums2 element squared against nums1 pairs. After calculation, we get 2 valid triplets total.

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to recognize this as a frequency counting problem where we need to match squares with products. The optimal approach uses hash maps to count element frequencies, then for each unique value, calculates how many valid triplets can be formed using combinatorics. Best approach is frequency counting with Time: O(n²+m²), Space: O(n+m).

Common Approaches

✓ Brute Force

⏱️ Time: O(n²m + m²n) Space: O(1)

For each element in nums1, check all pairs in nums2 to see if square equals product. Then do the same for elements in nums2 with pairs in nums1.

Frequency Count Optimization

⏱️ Time: O(n²+m²) Space: O(n+m)

Build frequency maps for both arrays, then for each unique value, calculate how many valid triplets can be formed using combinatorics.

Brute Force — Algorithm Steps

Check Type 1: For each nums1[i]², find all pairs (j,k) where nums2[j] * nums2[k] equals it
Check Type 2: For each nums2[i]², find all pairs (j,k) where nums1[j] * nums1[k] equals it
Sum all valid triplets found

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Type 1

For each nums1[i]², check all pairs in nums2

Check Type 2

For each nums2[i]², check all pairs in nums1

Count Matches

Sum all valid triplets found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int count = 0;
    
    // Type 1: nums1[i]² == nums2[j] * nums2[k]
    for (int i = 0; i < nums1Size; i++) {
        long long target = (long long)nums1[i] * nums1[i];
        for (int j = 0; j < nums2Size; j++) {
            for (int k = j + 1; k < nums2Size; k++) {
                if ((long long)nums2[j] * nums2[k] == target) {
                    count++;
                }
            }
        }
    }
    
    // Type 2: nums2[i]² == nums1[j] * nums1[k]
    for (int i = 0; i < nums2Size; i++) {
        long long target = (long long)nums2[i] * nums2[i];
        for (int j = 0; j < nums1Size; j++) {
            for (int k = j + 1; k < nums1Size; k++) {
                if ((long long)nums1[j] * nums1[k] == target) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse nums1
    int nums1[1000], nums1Size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse nums2
    int nums2[1000], nums2Size = 0;
    token = strtok(line, "[,]");
    while (token != NULL) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums1, nums1Size, nums2, nums2Size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m + m²n)

For each element in nums1 (n), check all pairs in nums2 (m²), plus for each element in nums2 (m), check all pairs in nums1 (n²)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for counters

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

456 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways Where Square of Number Is Equal to Product of Two Numbers - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler