Tuple with same product

Array Hash Table Counting

70.1% acceptance

Feb 25, 2026

1372

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of nums, and a != b != c != d.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut product_count: HashMap<i32, i32> = HashMap::new();
    for i in 0..n {
      for j in i + 1..n {
        *product_count.entry(nums[i] * nums[j]).or_insert(0) += 1;
      }
    }
    // For each product with k pairs, choose 2 pairs: k*(k-1)/2 combinations, each gives 8 tuples
    product_count.values().map(|&k| k * (k - 1) / 2 * 8).sum()
  }
}