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 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:
- Code is written in Python 3 using utf-8 charset
- Time complexity is on the higher side, O(n). It can be improved, but I am just bored.
- This code is lovely anyway.
- Yes, I do know few things now.
- This code question was asked in a Google interview.
- Recursion doesn’t necessarily means improvement of the problem-solving capability of your code. Use it wisely. I don’t!
- I don’t like complicated things unless they are human emotions and needs.
Please ask questions anonymously, if you feel shy!