New Year Day, 01-01-2024

It's the first day of 2024. The clock has just hit 3 in the afternoon and it has been a perfect day so far.

I thought of writing a blog in this busy schedule, well it just takes a few minutes( thanks to my touch typing ), and this is what is great about such improvements in our daily lives, a skill a day keeps time problems at bay.

Yesterday I solved the last POTD of 2023 of GFG. The problem was quite easy considering that you have fair amount of experience solving problem of Recursion + Memoisation, if you do, then this would be a piece of cake for you nothing else. 

We are just checking whether there are numbers in array that would sum up to be multiples of 20, 24 or 2024. The part that alerts me about the problem being of this particular type is the uncertainty hidden in it, cause if you think about it, imagine any array of size 5 or 6 with any random numbers, then there are so many possibilities of getting multiples of 20, 24 or 2024, cause the thing that's happening here is that for every elem of array we have 2 choices, either that number will be present in the array or it will be absent.

For example, that this array, [2,43,3,5,4,19,9,5,9,4,7,1] now just take a couple of minutes to think how you can get a summation that would be a multiple of either of the numbers I mentioned before. 

You might have thought of 19+5 being 24 or 43+5 being 48, but did you see the 2+3+5+9+5 being 24??

This is the real problem, we humans need to go through a lot of possibility checking the conditions, and also we can't garner the power of memoisation with us can we?

This is where we need this approach of dealing with such kinds of problem statements.

Explanation:

The code is straightforward, just divide into parts, the conditions in the starting of the solve func are the base conditions that will stop the recursion, there are 2 possibilities for every elem in array, either we take it( in that case we get it's contribution in the currSum ) or we don't take the elem and just go to the next elem.

There is a DP( just a naming convention when we are using the approach of Dynamic Programming, can take any name ) array that will store the intermediate results during the recursion, bcz... if you think about it, then 2 choices for every elem will lead of 2^n no. of cases and that would require a time complexity of O(2^n) and we would neve want that, atleast I won't. So we gotta do something for that isn't it?

We can simply understand dp as a means of storing the intermediate results, that would just lead us to accessing the DP that is of size n*(summation of elems in array+1) so we reduce that 2^n to this O(n*(summation of elems)).

This is the beauty of this approach.

Try to implement the code by yourself first then if you get problems, try to solve them, then if you require... then you can take a look at the provided code.

Code Implementation:

from typing import List

class Solution:

       

    def solve(self,n,coins,currInd,currSum,dp):

           

        if(currInd>=(n-1)):

            # the no. of coins should be multiple of either 20,24 or 2024 but not 0, cause

            # we can't purchase anything with 0 coins

            if(currSum!=0 and (currSum%20==0 or currSum%24==0 or currSum%2024==0)):

                dp[currInd][currSum]=True

                return True

               

            if((currSum+coins[currInd])%20==0 or (currSum+coins[currInd])%24==0

                or (currSum+coins[currInd])%2024==0):

                dp[currInd][currSum]=True

                return dp[currInd][currSum]

            else:

                dp[currInd][currSum]=False

                return False

               

        # same explanation as above

        if(currSum!=0 and (currSum%20==0 or currSum%24==0 or currSum%2024==0)):

            dp[currInd][currSum]=True

            return dp[currInd][currSum]

       

        if(dp[currInd][currSum]!=-1):

            return dp[currInd][currSum]

           

        # either we take the current no. of coins in our total or we don't, 2 choices

        take=self.solve(n,coins,currInd+1,currSum+coins[currInd],dp)

        if(take==True):

            dp[currInd][currSum]=True

            return True

       

        notTake=self.solve(n,coins,currInd+1,currSum,dp)

       

        # will return True if either of take or notTake is True else will return False

        dp[currInd][currSum]=take or notTake

       

        # when it's not possible to get the summation of 20 or 24

        return dp[currInd][currSum]

   

    def isPossible(self, N : int, coins : List[int]) -> bool:

        # code here

       

        dp=[[-1 for i in range(sum(coins)+1)] for j in range(N)]

       

        ans=self.solve(N,coins,0,0,dp)

        # print(ans)

        return ans