Digital Specialist Engineer

Ninja and his friend are playing a game. They are having ‘N’ piles and each pile contains ‘A[i]’ amount of stones in it. Ninja will make the first move.

In each move, a player can choose any pile and remove any number of stones ( at least one ) from that pile. The player who cannot make a move loses the game.

Assuming both players play optimally, output 1 if Ninja wins the game and 0 if Ninja loses the game.

Example :

N = 3
A = [ 3, 4, 5 ]

Explanation : 

One of the optimal ways to play the game is : 

Ninja removes 3 stones from the first pile : [ 0, 4, 5 ].
Friend removes 3 stones from the second pile : [ 0, 1, 5 ].
Ninja removes 3 stones from the third pile : [ 0, 1, 1 ].
Friend removes 1 stone from the second pile : [ 0, 0, 1 ].
Ninja removes 1 stones from the third pile : [ 0, 0, 0 ].

Thus Ninja wins the game here.

On your birthday, your friends gifted you 'N' boxes of chocolates, which are represented as an array 'A' of 'N' positive integers where 'A[i]' denotes the number of chocolates in the i-th box. You want to give these boxes as return gifts to your guests but with an equal number of chocolates in each box. For that, you are going to perform the following operation on the boxes, where each operation is as follows:

Choose a positive integer 'x'.
If any of the boxes contains more than 'x' chocolates, take out the extra chocolates from that box, i.e., if 'A[i]' > 'x', make 'A[i]' = 'x'  ( for all 'i' where 1 <= 'i' <= 'N')

The cost of an operation is the total number of chocolates taken out from all the boxes, i.e., cost = (sum of 'A' before operation) - (sum of 'A' after operation).

Your task is to find the minimum number of operations such that there is an equal number of chocolates in each box and the cost of each operation does not exceed 'K'.

Note :

1. 'x' can be any positive integer of your choice. It may or may not be present in array 'A'.
2. 'K' is large enough to have at least one 'x' for the operation.

Example :

N = 4
K = 5
A = [ 5, 2, 3, 4 ]

In the first operation, choose x = 3, the updated array 'A' becomes [3, 2, 3, 3]. The cost of this operation is (5+2+3+4)-(3+2+3+3) = 3.

In the second operation, choose x = 2, the updated array 'A' becomes [2, 2, 2, 2]. The cost of this operation is (3+2+3+3)-(2+2+2+2) = 3.

After the second operation, all elements in array 'A' become equal. Hence return 2 as our final answer.

We can't choose x = 2 in our first operation, because (5+2+3+4)-(2+2+2+2) = 6 which exceeds K = 5.

Who is your ideal and why so?
How do you deal with failures?
Are you comfortable in relocating, in case the need arises?
Do you have any questions for me?