Painter's Partition Problem You are given two integers a and | Cse interview questions

Painter's Partition Problem

You are given two integers a and b and an array of integers C of size n.

There are a painters available and each of them takes b units of time to paint 1 unit of board. You have to paint all n boards [C0, C1, C2, C3 … Cn-1].

Calculate and return minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of board. Return the ans % 10000003

Note :

1. 2 painters cannot share a board to paint. That is to say, a board
cannot be painted partially by one painter, and partially by another.

2. A painter will only paint contiguous boards. Which means a
configuration where painter 1 paints board 1 and 3 but not 2 is
invalid.

Input Format :

The first argument is integer a.
The second argument is integer b.
The third argument the integer array C.

Output Format :
Return (minimum time required to paint all boards under the constraints that any painter will only paint contiguous sections of board) % 10000003.

Constraints :

1 <= a <= 1000
1 <= b <= 10^6
1 <= C.size() <= 10^5
1 <= C[i] <= 10^6

Examples :

Input 1 :
a = 2
b = 5
c = [1, 10]

Output 1 :
50

Explanation 1 :

There are 2 painters each with capability of painting 1 unit of board in 5 units of time.

Possibility 1 : Same painter can paint both the blocks. So time taken will be 1*5 + 10*5 = 55 time units.

Possibility 2 : We can employ two different painters for two boards. These 2 painters will work in parallel and time taken by them will be 1*5 and 10*5 ie 5 and 50 units of time. So time taken to paint both the boards will be max(5, 50) which is 50.

Among both the possibilities, later takes minimun time. So output 50 % 10000003 which is 50 itself.

Input 2 :
a = 10
b = 1
c = [1, 8, 11, 3]

Output 2 :
11

Explanation 2 :

There are 10 painters each with capability of painting 1 unit of board in 1 units of time.
So we can employ 4 painters for four boards with given lengths 1, 8 , 11 and 3. These 4 painters will work in parallel and time taken by them will be 1, 8, 11 and 3 units of time. So time taken to paint all boards will be max(1, 8, 11, 3) which is 11. So output 11 % 10000003 which is 11 itself.

Topic : Binary Search

Reference -> InterviewBit, GeeksToCode

Solution -> GeeksforGeeks - Set 1, Set 2

Asked in Google, Codenation

Join our Official Channel @cseinterview