you can use bit masking here.

for any number i from 1 — 2^10

ans[i] = maximum number in the original array which consist of digits same as the set bits in number i,

ex — i = 7, ans[i] = maximum number in the original array which consists of digits 0, 1, 2 as 2^0 + 2^1 + 2^2 = 7

now after calculating maximums you can find maximum ans by considering two numbers i,j in range 1 — 2^10

if((i&j)==0) final_ans = max(final_ans,ans[i]+ans[j])

def max_sum_without_common_digit(nums): max_num = {} max_sum = -1

for num in nums:
    max_val = int(''.join(sorted(str(num), reverse=True)))
    max_num[max_val] = max(max_num.get(max_val, 0), num)

for num in nums:
    for key in max_num.keys():
        if not any(digit in str(num) for digit in str(key)):
            max_sum = max(max_sum, num + max_num[key])

return max_sum

nums = [15, 0, 105] print(max_sum_without_common_digit(nums))

int solution(vector<int>& nums) {
    unordered_map<int, int> max_num;
    int max_sum = -1;
    for (int num : nums) {
        string num_str = to_string(num);
        sort(num_str.rbegin(), num_str.rend());
        int max_val = stoi(num_str);
        max_num[max_val] = max(max_num[max_val], num); 
    }
    for (int num : nums) {
        string num_str = to_string(num);
        for (auto& it : max_num) {
            string key_str = to_string(it.first);
            if (none_of(key_str.begin(), key_str.end(), [&num_str](char c) { return num_str.find(c) != string::npos; })) { 
                max_sum = max(max_sum, num + it.second);
            }
        }
    }

    return max_sum;
}

Working well on TC's

We can use Bitmasking to represent the digits present in each number. There are only $$$2^{10} = 1024$$$ possible unique digit combinations (masks) :

1. For each mask, we only store the maximum element that uses that exact set of digits. (For example, both 503 and 305 share the same digit mask, but we strictly store 503 because we want to maximize our final sum).
2. We iterate over all valid masks. For each mask, we calculate its complement (which represents all the digits not used by the current number).
3. We iterate over all valid submasks of this complement. This guarantees we only check numbers that share absolutely no digits with our current mask.
4. We find the maximum element from all these valid submasks, and update our answer: ans = max(ans, currMax + submaskMax).

Maximum Time Complexity -> O(1024 * 1024)

Approach: Bitmasking

We need to select two numbers such that: 1. Their sum is maximum. 2. They do not share any common digit. Example: 123 and 45 can be selected because their digit sets {1, 2, 3} and {4, 5} are disjoint. Since decimal digits range from 0 to 9, we use 10 bits to represent the digits present in a number. - Bit 0 represents digit 0. - Bit 1 represents digit 1. - ... - Bit 9 represents digit 9. If a digit is present in a number, its corresponding bit is set to 1. Example: Number = 123 cpp mask = (1 << 1) | (1 << 2) | (1 << 3); mask = 2 + 4 + 8 = 14;

Code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> masks(1 << 10, 0);
    int temp, mask;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        int x = temp;
        mask = 0;
        while (temp)
        {
            int last_digit = temp % 10;
            mask |= (1 << last_digit);
            temp /= 10;
        }
        masks[mask] = max(masks[mask], x);
    }
    int ans = 0;
    for (int i = 0; i < 1024; i++)
    {
        for (int j = 0; j < 1024; j++)
        {
            if ((i & j) == 0)
                ans = max(ans, masks[i] + masks[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

Code Explanation

1. Initialize all possible masks cpp vector<int> masks(1 << 10, 0); There are (2^{10} = 1024) possible masks, ranging from 0 to 1023. masks[mask] stores the maximum input number having that digit mask. We only need the maximum number for each mask because numbers with the same mask have identical digit compatibility with other numbers. 2. Build the digit mask cpp while (temp) { int last_digit = temp % 10; mask |= (1 << last_digit); temp /= 10; } For 123: - Extract digit 3 and set bit 3. - Extract digit 2 and set bit 2. - Extract digit 1 and set bit 1. The resulting mask is 14. cpp masks[mask] = max(masks[mask], x); This stores the largest number having that mask. 3. Check whether two masks share digits cpp if ((i & j) == 0) The bitwise AND operator & identifies bits set in both masks. - If (i & j) != 0, the masks share at least one digit. - If (i & j) == 0, the masks have no common digits. 4. Calculate the maximum sum cpp ans = max(ans, masks[i] + masks[j]); We check every pair of compatible masks and update ans with the maximum sum.

Complexity Analysis

Let n be the number of input elements and D the maximum number of digits in a number. - Building masks: (O(nD)) - Checking all pairs of masks: (O(1024^2) = O(2^{20})) - Extra space: (O(1024)) Overall time complexity: (O(nD + 2^{20})) Note: This implementation assumes non-negative input numbers and initializes the answer to 0. If the input can contain 0, handle it explicitly by setting its digit mask to 1 (bit 0). Also, if two distinct input elements must be selected, the code should account for that requirement when considering identical masks.