Practice Projects

Tuple with Same Product

Problem Statement

  • aapko ek array nums di gayi hai jo distinct positive integers se bani hai. Aapko aise tuples (a, b, c, d) ka count return karna hai jahan a * b = c * d ho. Bas kuch shartein hain:

    a, b, c, aur d nums ke elements hone chahiye.

    Aur yeh sab ek dusre se alag hone chahiye, yaani a != b != c != d.

    Example 1:

    Input: nums = [2,3,4,6]

    Output: 8

    Explanation:

    Valid tuples hain:

    (2,6,3,4)

    (2,6,4,3)

    (6,2,3,4)

    (6,2,4,3)

    (3,4,2,6)

    (4,3,2,6)

    (3,4,6,2)

    (4,3,6,2)

    Example 2:

    Input: nums = [1,2,4,5,10]

    Output: 16

    Explanation:

    Valid tuples hain:

    (1,10,2,5)

    (1,10,5,2)

    (10,1,2,5)

    (10,1,5,2)

    (2,5,1,10)

    (2,5,10,1)

    (5,2,1,10)

    (5,2,10,1)

    (2,10,4,5)

    (2,10,5,4)

    (10,2,4,5)

    (10,2,5,4)

    (4,5,2,10)

    (4,5,10,2)

    (5,4,2,10)

    (5,4,10,2)

    Constraints:

    nums.length 1 se 1000 ke beech hona chahiye.

    nums[i] 1 se lekar 10,000 tak ke distinct positive integers hone chahiye.

    Aapko yeh tuples find karne hain jo in conditions ko satisfy karte hain.

Practice Projects

Tuple with Same Product

Intuition yeh hai ki humein (a, b, c, d) tuples ka count karna hai jahan a * b = c * d ho. Sabhi possible 4-tuples ko check karna inefficient hoga, kyunki yeh time-consuming process hai.Isliye, hum ek hashmap (yaani ek dictionary) ka istemal kar sakte hain. Yeh hashmap har possible product ka frequency track karega jo 2 numbers ko multiply karne se milta hai. Hum har pair (i, j) ke product ko hashmap mein store karenge.Yeh steps hai: Pehle, array ke har pair (i, j) ka product calculate karo aur hashmap mein store karo. Hashmap ki key product hogi aur value product ki frequency hogi.Jaise hi kisi pair ka product already hashmap mein exist karta hai, iska matlab hai ki koi aur pair bhi wahi product de raha hai. Isliye hum pairs ka count badhate rahenge.Is process se humein efficiently tuples ka count mil jayega jo a * b = c * d ko satisfy karte hain.

Intuition

Saare pairs (i, j) aur unke products compute karo:Har possible pair (i, j) ka product nikal lo. Jaise agar nums = [2, 3, 4, 6] hai, toh (2 * 3 = 6), (2 * 4 = 8), (2 * 6 = 12), aur aise hi sabhi pairs ka product calculate karna hai.Product frequencies ko hashmap mein store karo:Ek hashmap banao jisme key product hoga aur value us product ka frequency count hoga. Jaise agar product 12 do alag-alag pairs se aa raha hai, toh hashmap mein 12 ka count 2 hoga.Har naye pair (x, y) ke liye check karo agar product = x * y map mein exist karta hai:Agar koi naya pair (x, y) lete hain aur uska product hashmap mein already exist karta hai, toh iska matlab pehle bhi kuch pairs aise the jo wahi product de rahe the.Us product se saari previous occurrences ke saath pair karo → 8 × count(product) naye tuples banenge:Yeh confirm karke ki product pehle se exist kar raha hai, hum us product se banne wale saare previous pairs ko count kar sakte hain. Har pair ke combination se 8 naye valid tuples banenge.Future pairs ke liye hashmap update karo:Har naye pair (x, y) ke product ko hashmap mein update karte raho taaki future comparisons ke liye ready ho.

Approach

Time Complexity: O(n²)

Is problem ka time complexity O(n²) hai. Yeh isliye kyunki humein har possible pair (i, j) ka product calculate karna padta hai. Given ki nums array mein n elements hain, toh humein roughly n * (n – 1) / 2 pairs consider karne padte hain. Isi wajah se time complexity quadratic, yaani O(n²) hoti hai.

Space Complexity: O(n²)

Space complexity bhi O(n²) hoti hai. Yeh isliye kyunki humein har unique product ke liye frequencies ko track karna padta hai hashmap (ya dictionary) mein. Given ki there are n * (n – 1) / 2 possible pairs, worst case mein humein in saare products ko store karna padta hai. Isliye space complexity bhi quadratic hoti hai, yaani O(n²).

Solution

				
					var tupleSameProduct = function(nums) {
    // Ek hashmap (Map) banate hain product counts store karne ke liye aur result ko 0 set karte hain
    let productCount = new Map(), result = 0;

    // Pehla loop: har element ke liye iterate karte hain
    for (let i = 0; i < nums.length; i++)
        // Dusra loop: current element ke baad ke elements ke liye iterate karte hain
        for (let j = i+1; j < nums.length; j++) {
            // Pair ka product calculate karte hain
            let product = nums[i] * nums[j];

            // Agar product hashmap mein pehle se exist karta hai,
            // toh result ko update karte hain with 8 * frequency of that product
            result += 8 * (productCount.get(product) || 0);

            // Product ko hashmap mein update karte hain
            // Agar pehle se nahi hai toh 1 set karte hain, aur agar hai toh +1 badhate hain
            productCount.set(product, (productCount.get(product) || 0) + 1);
        }

    // Final result return karte hain
    return result;
};

  1. Initialize:

    • productCount ek hashmap (Map) hai jo har product ka count store karega.

    • result variable ko 0 se initialize karte hain jisme valid tuples ka count store hoga.

  2. Outer Loop:

    • Pehle loop mein, i index se har element ke liye iterate karte hain.

  3. Inner Loop:

    • Dusre loop mein, i+1 se start karke har element ke liye iterate karte hain. Yani hum current element ke baad ke sabhi elements ko check karte hain.

  4. Calculate Product:

    • Har pair ka product calculate karte hain, jise nums[i] * nums[j] karte hain.

  5. Update Result:

    • Hashmap check karte hain agar yeh product pehle se exist karta hai. Agar karta hai, toh us product ke frequency count ko 8 se multiply karke result mein add karte hain. (8 isliye kyunki har occurrence ke sath 8 naye tuples ban sakte hain).

  6. Update Hashmap:

    • Product ko hashmap mein update karte hain. Agar product pehle se hashmap mein nahi hai, toh uska count 1 set karte hain. Agar hai, toh uske count ko 1 se increment karte hain.

  7. Return Result:

    • Finally, result return karte hain jisme saare valid tuples ka count hoga.

 

Solution

				
					#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        // Ek hashmap (unordered_map) banate hain jo product counts ko store karega
        unordered_map<int, int> mp;
        // ans variable ko 0 se initialize karte hain jo valid tuples ka count store karega
        int ans = 0, n = nums.size();
        
        // Pehla loop: Har element ke liye iterate karte hain
        for (int i = 0; i < n; i++)
            // Dusra loop: Current element ke baad ke elements ke liye iterate karte hain
            for (int j = i + 1; j < n; j++) {
                // Pair ka product calculate karte hain
                int product = nums[i] * nums[j];
                
                // Agar product hashmap mein pehle se exist karta hai,
                // toh ans ko update karte hain with 8 * frequency of that product
                ans += 8 * mp[product];
                
                // Product ko hashmap mein update karte hain
                // Agar pehle se nahi hai toh 1 set karte hain, aur agar hai toh +1 badhate hain
                mp[product]++;
            }
        
        // Final result return karte hain
        return ans;
    }
};

      • Initialize Data Structures:

        • Start by creating a hashmap (or dictionary) to store the product of pairs and their corresponding frequency (count).

        • Also, initialize a variable to keep track of the result, which will store the number of valid tuples.

      • Loop Through All Pairs:

        • Use two nested loops to go through all possible pairs (i, j) in the array.

        • The outer loop iterates over each element starting from the first one.

        • The inner loop iterates over each element that comes after the current element of the outer loop.

      • Calculate Product:

        • For each pair (i, j), calculate the product of the two elements.

      • Update Result:

        • Check if this product already exists in the hashmap.

        • If it does, it means there are previous pairs that have the same product. For each occurrence of that product, 8 new valid tuples can be formed. Multiply the frequency of the product by 8 and add this value to the result.

      • Update Hashmap:

        • Update the hashmap by increasing the frequency of the current product by 1. If the product does not already exist in the hashmap, add it with an initial frequency of 1.

      • Return the Result:

        •