1_Hypex_'s blog

Please help to solve this problem
By 1_Hypex_, history, 12 months 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 (16)
| Write comment?
»
12 months ago, # |
← 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
  • »
    »
    12 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Thanks a lot! Really appreciate!

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice solution..but how do we find maximum number in the array consisting of digits same as set bits faster?

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      iterate over all elements of the array, for any element get all the digits in it and update the corresponding mask value

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you please explain for Testcase [15,0,105] Output is 15

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sum of 15 and 0 is 15

          15 and 0 have no common digits between them. Since 105 can't be paired with any other element, and we have to output sum of two elements, we print 15.

          → Reply
»
9 months ago, # |
  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
  • »
    »
    9 months ago, # ^ |
    ← 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
    • »
      »
      »
      9 months ago, # ^ |
      ← 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
»
9 months ago, # |
← 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
  • »
    »
    9 months ago, # ^ |
    ← 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I actually Submitted this code after getting tle on brute force code and it went well foe hidden cases too !!

      It worked well on OA

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you share the problem link?

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          It was asked in an Online Assessment and I submitted this code there and it passed all hidden cases too

          → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        sorry, I didn't know everything about your code, so I just wrote what I saw and thought it would get Time Limit verdict.

        → Reply