MAX AND MOD

Hey guys this is your friend prabha!

I was solving a leetcode problem and encountered an error which made me think a lot. If you are too tired, just go to the summary and take the mantra, otherwise, fasten your seat belts.

The problem I was solving is *Get the maximum Score. *In the section below, I have poured my thought process. If you just want the math and the problem I faced, skip to MAX AND MOD.

PROBLEM SOLVING

Before my explantion and thought process do read the question. Think about the approach you could arrive at. If you could find a solution with similar thought process as the one below, lemme know!

Given two arrays nums1 and nums2 which are strictly increasing in nature. If they share a common node, you can switch paths between them. The goal is to maximise the path sum. The answer should be retured in modulo since the result would be very big.

I thought it as a DP approach for 2 major reasons. The ideas of pick and not_pick . This gives 2 state idea, whether I am going forward or branch. The second reason is maximising.

Skim through the code below before reading this idea!

So what did I do?

• I found the intersecting points.
• Enumerated the value with index. Since it’s strictly increasing there are no duplicates. Stored them as left and right .
• Wrote a recursive call with a flag.
• The flag decides which nums I am in. If flag is true then I am in nums2.
• Now, if it is a common element, I have an option — we can move forward or continue moving on the same path.
• I switched flags to choose indexes.

The given code is a non-optimal approach which will give you a better intuition.

#ins't it pretty doable?
class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        l1,l2 = len(nums1),len(nums2)
        left = {num:i for i,num in enumerate(nums1)}
        right = {num:i for i,num in enumerate(nums2)}
        s = set(nums1) & set(nums2)
        MOD = 10**9+7
        print(s,len(s))
        @cache
        def dp(idx1,idx2,flag): #flag true na nums2
            #print(idx1,idx2,flag)
            if (not flag and idx1 == l1) or (flag and idx2 == l2):
                return 0
            #choose 2 paths either procceed further or branch?
            ans = nums2[idx2] if flag else nums1[idx1]
            if flag:
                choose = 0
                if nums2[idx2] in s:
                    choose = dp(left[nums2[idx2]] + 1,idx2,False)
                not_choose = dp(idx1,idx2+1,True)
                return (max(choose,not_choose)+ans)
            else:
                choose = 0
                if nums1[idx1] in s:
                    choose = dp(idx1,right[nums1[idx1]] + 1,True)
                not_choose = dp(idx1+1,idx2,False)
                return (max(choose,not_choose)+ans)
        return max(dp(0,0,True),dp(0,0,False))%MOD
        # return 0

You could see one variable is not being used here, either the idx2 in choose of True flag, or the idx1 in not_choose. Similarly on False flag. So we can remove this and maintain a single index. I have optimised the above code in further sections.

My thought process didn’t complete here, I am overly concerned about modulo and overflow, then the rest is history. Have a fun read!

MAX AND MOD

Let’s forget the problem statement now and get into the constraints and modulo.

As you could see, the final answer should be returned after modulo since it can be really large. And traditionally we use MOD = 109+7.** So why do we need modulo? in simple terms we need it to reduce overflows in problems to get the final answer in the given range and to avoid excessive calculation to make the logic and algorithm work efficently.

*10*9+7 is a prime number. Why a prime number? Because non-prime numbers breaks in division arithemtic but passes addition, subtraction and multiplication. To be more specific prime number guarantees a multiplicative inverse making division possible. Non-prime modulo can break division since inverses may not exist. The proof of work is discussed in Fermat’s little theorem, it’s a fun read so do try.

Now to the error I made while coding, the code snippet you see below is the erroneous code. Can you find what’s the error? Just focus on the MOD part, the logic is perfect.

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        l1,l2 = len(nums1),len(nums2)
        left = {num:i for i,num in enumerate(nums1)}
        right = {num:i for i,num in enumerate(nums2)}
        s = set(nums1) & set(nums2)
        MOD = 10**9+7
        print(s,len(s))
        @cache
        def dp(idx,flag): #flag true na nums2
            #print(idx1,idx2,flag)
            if (not flag and idx == l1) or (flag and idx == l2):
                return 0
            #choose 2 paths either procceed further or branch?
            ans = nums2[idx] if flag else nums1[idx]
            if flag:
                choose = 0
                if nums2[idx] in s:
                    choose = dp(left[nums2[idx]] + 1,False)
                not_choose = dp(idx+1,True)
                return (max(choose,not_choose)+ans)%MOD
            else:
                choose = 0
                if nums1[idx] in s:
                    choose = dp(right[nums1[idx]] + 1,True)
                not_choose = dp(idx+1,False)
                return (max(choose,not_choose)+ans)%MOD
        return max(dp(0,True),dp(0,False))%MOD
        # return 0

I was breaking my head where I was going wrong! Then my man Venkata Ramana Rao came for THE DEBUGGING SESSION. He is the one who figured it out. Did you?

If yes then good! If not we are in the same boat buddy. Lemme tell ya. Let’s take an example to understand where I have went wrong.

choose = 10^9+8
not_choose = 5

Wait! you can ask me you have took MOD only in the final return statement but how do you claim choose and not_choose as per example. As per the recursive call and problem the accumulated sum can be like this. Because effectively each return value is MODed and the resultant is maxed.

So what do we get?

choose % MOD = 1
not_choose % MOD = 5
max(choose,not_choose) = 5

#But choose is the bigger one!

One the other reason it fails is that MOD is smaller than the number and we start comparing the remainders. We just need THE FINAL answer in modulo. Not the comparison!

So what did we learn? Modulo breaks the ordering of comparison. This is also true for any comaprsion: >, <, max, min. In the previous problems I have solved I used it over +, -, * which reduced the computation cost.

The correct code is just removing those MOD in the return statement of the dp.

class Solution:
    def maxSum(self, nums1: List[int], nums2: List[int]) -> int:
        l1,l2 = len(nums1),len(nums2)
        left = {num:i for i,num in enumerate(nums1)}
        right = {num:i for i,num in enumerate(nums2)}
        s = set(nums1) & set(nums2)
        MOD = 10**9+7
        print(s,len(s))
        @cache
        def dp(idx,flag): #flag true na nums2
            #print(idx1,idx2,flag)
            if (not flag and idx == l1) or (flag and idx == l2):
                return 0
            #choose 2 paths either procceed further or branch?
            ans = nums2[idx] if flag else nums1[idx]
            if flag:
                choose = 0
                if nums2[idx] in s:
                    choose = dp(left[nums2[idx]] + 1,False)
                not_choose = dp(idx+1,True)
                return (max(choose,not_choose)+ans) #%MOD
            else:
                choose = 0
                if nums1[idx] in s:
                    choose = dp(right[nums1[idx]] + 1,True)
                not_choose = dp(idx+1,False)
                return (max(choose,not_choose)+ans) #%MOD
        return max(dp(0,True),dp(0,False))%MOD
        # return 0

If you felt you dind’t get the above example, here is a much smaller one.

mod = 7
choose = 32
not_choose = 27

#what does max(choose%MOD,not_choose%MOD) gives?

#what does max(choose,not_choose) give?

SUMMARY

Taking MOD while comapring numbers higher than the MOD value breaks the comparsion. Don’t use MOD while you are comparing. The above example will make you understand.

If you have read till this point, thanks for your support and patience. Will post silly and interesting things here.