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

skill issue

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

Thanks a lot! Really appreciate!

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

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

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

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.def max_sum_without_common_digit(nums): max_num = {} max_sum = -1

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

you can use five

`~`

symbols before and after your code to make it look more readable.`~~~~~

Your code here...

~~~~~`

(ignore ` symbols)

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

Working well on TC's

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.

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

Can you share the problem link?

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

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

No worries :)