Practice Projects

Max Sum of a Pair With Equal Sum of Digits

Problem Statement

  • Aapko ek 0-indexed array diya gaya hai jiska naam hai nums aur isme sirf positive integers hain. Aapko aise do indices i aur j chunne hain, jinka sum of digits same ho aur i ≠ j ho.

    Aapko maximum value of nums[i] + nums[j] return karni hai jo aapko sabse zyada mil sakti hai aise indices i aur j me se jo in conditions ko satisfy karte hain.

    Example 1:

    Input: nums = [18,43,36,13,7] Output: 54

    Explanation:

    • (i, j) kaunse pairs conditions satisfy karte hain:

      • (0, 2), dono numbers ka sum of digits 9 hai, aur inka sum 18 + 36 = 54 hai.

      • (1, 4), dono numbers ka sum of digits 7 hai, aur inka sum 43 + 7 = 50 hai.

    To maximum sum jo humein milta hai wo 54 hai.

    Example 2:

    Input: nums = [10,12,19,14] Output: -1

    Explanation: Koi bhi do numbers in conditions ko satisfy nahi karte, to hum -1 return karte hain.

    Constraints:

    1. 1 <= nums.length <= 105

    2. 1 <= nums[i] <= 109

Practice Projects

Max Sum of a Pair With Equal Sum of Digits

Sum of Digits Calculation:

Har number ke liye, uske sum of digits ko calculate karo using division aur modulo operations. Example: 18 ka sum of digits 1 + 8 = 9 hoga.

Track Maximum Values:

Ek array banao size 82 ka (max digit sum 81 ho sakta hai). Is array mein har possible digit sum ke liye sabse bada number store karna hai. Agar ek dusra number milta hai jiska digit sum same hai, toh unka sum calculate karo aur maximum result update karo agar needed ho.

Efficient Updates:

Har sum of digits ke liye maximum number ko track karte raho taaki redundant calculations avoid ho sakein.

The Plan to solve the Problem

Time Complexity: O(nlogm)

  • Hum har number ko ek baar process karte hain, isliye overall processing time O(n) hota hai, jaha n array ka size hai.

  • Ek number ka sum of digits calculate karne ke liye division aur modulo operations use karte hain, jo O(logm) time leta hai, jaha m sabse bada number hai.

To combined time complexity hai O(nlogm).

Space Complexity: O(1)

  • Hum ek fixed size array use karte hain (size 82) maximum values store karne ke liye.

  • Yeh array ki size constant hai, chahe array nums ki size kuch bhi ho.

Isliye, space complexity O(1) hoti hai.

Solution

				
					var maximumSum = function(nums) {
    // Ek array banao size 82 ka aur usko 0 se fill kar do
    let max = new Array(82).fill(0);
    // Result ko -1 se initialize kar do
    let ans = -1;

    // Har number ke liye loop chalao
    for (let x of nums) {
        // Sum aur temporary variable initialize karo
        let sum = 0, temp = x;

        // Jab tak temp 0 nahi hota, sum of digits calculate karo
        while (temp !== 0) {
            sum += temp % 10; // Last digit ko sum mein add karo
            temp = Math.floor(temp / 10); // Last digit ko remove kar do
        }

        // Agar same sum of digits ke liye pehle se value hai to maximum sum update karo
        if (max[sum] !== 0) ans = Math.max(ans, x + max[sum]);
        
        // Current number ko maximum value update karo
        max[sum] = Math.max(max[sum], x);
    }

    // Final answer return karo
    return ans;
};

  • Array Initialization: Pehle ek array banaya jaata hai jiska size 82 hota hai aur sab elements ko 0 se fill kiya jaata hai. Yeh array use hota hai har possible sum of digits ke maximum value ko track karne ke liye.

  • Result Initialization: Hum ans variable ko -1 se initialize karte hain jo final result store karega.

  • Loop Through Numbers: Har number ke liye hum ek loop chalaate hain.

  • Sum of Digits Calculation: Har number ka sum of digits calculate karte hain. Iske liye hum number ko repeatedly 10 se divide karte hain aur remainder (last digit) ko sum mein add karte hain, tab tak jab tak number 0 nahi ho jaata.

  • Maximum Sum Calculation: Agar same sum of digits ke liye pehle se koi number array mein stored hai, toh hum un dono numbers ka sum calculate karte hain aur maximum result ko update karte hain agar yeh naya sum zyada ho.

  • Update Maximum Value: Current number ko array mein uske sum of digits ke corresponding index pe store karte hain agar yeh number wahan already stored number se bada ho.

  • Return Result: Loop ke baad, hum final result (ans) return karte hain jo maximum sum hoga jo hum find kar sakte hain given conditions ke according.

Solution

				
					class Solution {
public:
    int maximumSum(vector<int>& nums) {
        // Ek array banate hain size 82 ka aur usko 0 se initialize karte hain
        int max[82] = {0};
        // Result ko -1 se initialize karte hain
        int ans = -1;
        
        // Har number ke liye loop chalate hain
        for (int x : nums) {
            // Sum aur temporary variable initialize karte hain
            int sum = 0, temp = x;
            
            // Jab tak temp 0 nahi hota, sum of digits calculate karte hain
            while (temp != 0) {
                sum += temp % 10; // Last digit ko sum mein add karte hain
                temp /= 10; // Last digit ko remove karte hain
            }
            
            // Agar same sum of digits ke liye pehle se value hai to maximum sum update karte hain
            if (max[sum] != 0) ans = std::max(ans, x + max[sum]);
            
            // Current number ko maximum value update karte hain
            max[sum] = std::max(max[sum], x);
        }
        
        // Final answer return karte hain
        return ans;
    }
};