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:

- 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!

### Like this:

Like Loading...

*Related*