Painter’s Partition Problem

class Solution: 
    # @param A : integer 
    # @param B : integer 
    # @param C : list of integers 
    # @return an integer
    def partition(self, arr, n, k):     
        # One painter     
        if k==1:         
            return sum(arr[0:n])          

        # One Board to paint     
        if n==1:         
            return arr[0]          

        best = (2**31)-1     
        for i in range(1, n+1): 
            # find the best partition recursively
            best = min(best, max(self.partition(arr, i, k-1), sum(arr[i:n])))     
        return best           

    def paint(self, A, B, C):  
         # find the best possible partition from given values
         best = self.partition(C, len(C), A) 
         return (best*B)%10000003


Attributes of the algorithm:

  1. Code is written in Python 3 using utf-8 charset
  2. Time complexity is on the higher side, O(n). It can be improved, but I am just bored.
  3.  This code is lovely anyway.
  4.  Yes, I do know few things now.
  5.  This code question was asked in a Google interview.
  6.  Recursion doesn’t necessarily means improvement of the problem-solving capability of your code. Use it wisely. I don’t!
  7. I don’t like complicated things unless they are human emotions and needs.

Please ask questions anonymously,  if you feel shy!


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s