Software Developer

Given the count of total stones in a game. Two-player ‘Ale’ and ‘Bob’ are playing the game. Your task is to find who will win the game if both the players are playing optimally.

Rules of the game.

1. In a single turn, a player can choose a single stone or ‘even’ number of stones.

2. They will play alternatively, which means in the first chance ‘Ale’ will collect the stones, in second-chance ‘Bob’ will collect the stones. And always ‘Ale’ will start the game.

3. If any player is not able to take any stones then another player will win the game.

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

Let the array = [ 4, 2, 1, 5, 3 ]
Let pivot to be the rightmost number.

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

It was multiple coins concepts with the Arithmetic Progression formula on 2 Pointer's Method. We have to Iterate over a list of coins growing with a constant Difference, but the was to Make it more optimized.