Given a chocolate shop with chocolates priced from 1 to 10^9 consecutively. A student visits the shop for K consecutive days and buys chocolates indexed at (A1,A2,A3...An) on each day. You are given an array 'A' representing the chocolate indexes the student buys each day. Determine the minimum priced chocolate remaining in your shop after the kth day.

Constraints

1 <= N <= 500

1 <= A[i] < 10^9

1<=K<=10^5

Sample Test cases -

A = [1,3,5,7,9]

k = 3

O/P — 8

Explanation -

on 1st day 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (1,2,3,4,5,6,7,8,9.....10^9) ---> (2,4,6,8,10,11,12....10^9)

on 2nd day — again 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (2,4,6,8,10,11,12....10^9) ---> (4,8,11,13,15,16,17....10^9)

on 3rd day — again 1st , 3rd , 5th , 7th and 9th chocolate is removed. So the chocolate set becomes — (4,8,11,13,15,16,17....10^9) ---> (8,13,16,18,20,21,22....10^9)

Minimum priced chocolate after 3rd day is 8.

I was given 'n' rectangles represented by their diagonals on a 2-d plane. Then i would be asked multiple queries , in which i would be given an integer 'x' and i was asked to find the number of integer coordinates in the intersection regions of exactly 'x' rectangles. Suppose q = 4 , then i have to find the number of integer co-ordinates in the intersection region of exactly 4 rectangles . The rectangles could be in the form of a cluster so there could be more than one group of 4 rectangles , in that case i should return the sum of number of integer coordinates of all that intersections.

Constraints:-

Number of Rectangles — 0<n<10^5

Number of Queries — 0<n<10^5

Any tips would be helpful.

Given two arrays A and B of size n and m respectively. We can choose an element from A and one from B such that C=Ai + Bj . We have to compute all possible ways to from a sum C and also all unique sums.

Constraints:-

0<A,B<=10^5 // Size of array A and B

0<=Ai,Bi<=10^6

Sample I/P:-

2 3 //Size of array A and B

5 6 // Elements of array A

2 2 3 //Elements of array B

Sample O/P:-

7 2

8 3

9 1

Explanation:- 7 can be formed in two ways by A1+B1 , A1+B2 (using 1-based indexing)

8 can be formed in 3 ways by A1+B2 , A2+B1 , A2+B2

9 can be formed in 1 way by A2+B3

Please help me with a solution less than (n*m).

Have a look on my code:- Link here