### 1_Hypex_'s blog

By 1_Hypex_, history, 5 months ago,

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

• +4

 » 5 months ago, # |   -7 skill issue
 » 5 months ago, # | ← Rev. 2 →   +4 you can use bit masking here.for any number i from 1 — 2^10ans[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 = 7now after calculating maximums you can find maximum ans by considering two numbers i,j in range 1 — 2^10if((i&j)==0) final_ans = max(final_ans,ans[i]+ans[j])
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Thanks a lot! Really appreciate!
•  » » 5 months ago, # ^ |   0 Nice solution..but how do we find maximum number in the array consisting of digits same as set bits faster?
•  » » » 5 months ago, # ^ |   0 iterate over all elements of the array, for any element get all the digits in it and update the corresponding mask value
•  » » » » 7 weeks ago, # ^ |   0 Can you please explain for Testcase [15,0,105] Output is 15
•  » » » » » 7 weeks ago, # ^ |   0 sum of 15 and 0 is 1515 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.
 » 7 weeks ago, # |   0 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_sumnums = [15, 0, 105] print(max_sum_without_common_digit(nums))
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 you can use five ~ symbols before and after your code to make it look more readable.~~~~~Your code here...~~~~~(ignore  symbols)
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 #include int main(){ std::cout << "Hello, World!"; return 0; } (However, you have to write a code before a text).
 » 7 weeks ago, # | ← Rev. 4 →   0 int solution(vector& nums) { unordered_map 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
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 7 weeks ago, # ^ |   0 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
•  » » » » 7 weeks ago, # ^ |   0 Can you share the problem link?
•  » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 It was asked in an Online Assessment and I submitted this code there and it passed all hidden cases too
•  » » » » 7 weeks ago, # ^ |   +1 sorry, I didn't know everything about your code, so I just wrote what I saw and thought it would get Time Limit verdict.
•  » » » » » 7 weeks ago, # ^ |   +1 No worries :)