Microsoft OA | Nov 2023

Question

Given an array of length n. find the maximum pair sum which don't have common digits.
Example : n=6 , nums=[53,1,36,103,53,5]
in this case answer is 103+5 as they don't have common digits and maximum sum.
n<=10^5, nums[i]<=10^9
Note : if you can't find a pair, return -1;

Answer 1

// Convert any number into a mask (that has i^th digit = 1 if 'i' is a digit in num)
int mask(int num){
    int ans = 0;
    while(num){
        ans |= (1 << num%10);
        num /= 10;
    }
    return ans;
}

int solution(int n, int a[]){
    // dp[] will store the number in array a[] against its mask
    int dp[1<<10] = {-1}, ans = -1;
    
    for(int i=0; i<n; i++)
        dp[mask(a[i])] = a[i];
    
    // Iterate over all possible pairs of masks
    for(int i=0; i<(1<<10); i++){
        for(int j=i+1; j<(1<<10); j++){
            // Check for masks which do not have a digit in common, ie, "i&j = 0"
            if(dp[i] != -1 && dp[j] != -1 && (i&j) == 0)
                ans = max(ans, dp[i] + dp[j]);
        }
    }
    
    return ans;
}