### focus_on_cp's blog

By focus_on_cp, history, 3 months ago, Hello guys Recently I gave many tests and got frustated because I could not get many,but even after the test i tried ,but could not get ideas,can u give ideas,these questions are from mutiple company.

(sprinklr) 1)Given a array of n(<10^5) numbers and also a number k,WE have to divide into k continuous segments which covers the whole array so that maximum of all segments is minimum

eg)n=5,k=3 ,arr[]={5,10,30,20,15} it's optimal to take {5,10},{30},{20,15},so that maximum of sum of all numbers in the subarray is minimised here minimum possible is max(5+10,30,20+15)=35

in the task they mentioned that : expected time complexity:o(n*(log(m))),m=sum of all dishes time duration

(Graviton)

2)we have 3 containers .Each consists of nx,ny,nz balls respectively(1<=nx,ny,nz<=10^5).bag1 cotains nx balls and on each ball a number is written,similarly for other balls in all bags(numbers written on balls <10^5),you can pick one ball from each container ,find number of ways such that sum of selected numbers is divisible by 7.

eg)a={5,6} ,b={7} ,c={2,1}

ans=2; bec he can pick{5,7,2} or {6,7,1}

(De shaw)

3)You gave your younger sister a maths problem. She currently knows about digits, numbers, comparison of numbers, and operations on numbers. So, you gave her 9 boxes containing pieces with digits '1', '2'... '9' respectively. Each box contains infinite pieces. You also gave her a number X. Picking a piece i from ith box reduces the X by reduction[i]. Now, you asked her to create the largest possible integer using the above pieces given that

1. She can use multiple pieces from the same box.

2. At the end. X should be reduced to 0.

In the time your sister is solving the problem manually, you planned to write a code for the same. Output 0 if no such number is possible.

Input Format:

The first line of input comprises of the size of reduction) array N.

Next N lines contain N space-separated integers denoting reduction[i].

Next line consists of an integer X.

Output Format:

Output a single line containing the answer.

Constraints:

1<=X, reduction[i] <= 1000

Sample Input 0

9

10 4 3 8 9 3 4 3 5

10

sample output: 887

Explanation 0

reduction =[10, 4, 3, 8, 9, 3, 4, 3, 5]. X=10 , digit — 1 2 3 4 5 6 7 8 9 The largest number you can create is 887. Using digit 8 two times and 7 once will reduce X by 3*2+4=10. Therefore, in the end, X will be reduced to 0. 