1_Hypex_'s blog

Please help to solve this problem
By 1_Hypex_, history, 2 years ago, In English

Given an array of positive integers nums of length N, we need to find the maximum sum of two integers that do not have any common digit between them.

1<=N<=2e5 1<=nums[i]<=1e9

Eg. N = 6 nums = 53 1 36 103 53 5 ans = 103+5 = 108

This question was asked as part of Microsoft Online Assessment

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (17)
| Write comment?
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

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])

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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))

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    you can use five ~ symbols before and after your code to make it look more readable.

    `~~~~~

    Your code here...

    ~~~~~`

    (ignore ` symbols)

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it 
      #include <iostream>

int main(){
	std::cout << "Hello, World!";
	return 0;
}

      (However, you have to write a code before a text).

      → Reply
»
2 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it 
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

→ Reply
  • »
    »
    2 years ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    I see you are using two cycles, so I assume it will be TL under large constraints such as $$$n=2e5$$$ with a time limit of (usually) 1 second. Since there may be hidden constants and interruptions, the running time of this code may differ from the calculations.

    → Reply
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I guess this will work


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int get_digit_mask(int n) {
    int mask = 0;
    if (n == 0) {
        return 1; // Mask for digit 0 is 1 (2^0)
    }
    string s = to_string(n);
    for (char c : s) {
        mask |= (1 << (c - '0'));
    }
    return mask;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    
    vector<int> max_num_for_mask(1024, -1);

    for (int num : nums) {
        int mask = get_digit_mask(num);
        
        max_num_for_mask[mask] = max(max_num_for_mask[mask], num);
    }

    int max_sum = 0;

    for (int i = 1; i < 1024; ++i) {
        
        if (max_num_for_mask[i] == -1) {
            continue;
        }

        
        // For this problem, starting from i + 1 is fine since we need two different numbers.
        for (int j = i + 1; j < 1024; ++j) {
            
            if (max_num_for_mask[j] == -1) {
                continue;
            }

            if ((i & j) == 0) {
                max_sum = max(max_sum, max_num_for_mask[i] + max_num_for_mask[j]);
            }
        }
    }

    cout << max_sum << endl;

    return 0;
}
→ Reply