# Daily Coding Challenge #51

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.
Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.
*/

class Solution {
public:
int arrangeCoins(int n) {
// gauss' formula
// k(k+1)/2<=n
// k(k+1/2)^2-1/4<=n
// k=sqrt(2n+1/4)-1/2
return sqrt(2*(long long)n+0.25)-0.5;
}
};
``````

``````/*
LeetCode - Prison Cells After N Days

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation:
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

cells.length == 8
cells[i] is in {0, 1}
1 <= N <= 10^9
*/

class Solution {
public:
vector<int> prisonAfterNDays(vector<int>& cells, int N) {
// Every 14 days the cells will be same
// i.e. 6C2-1 (6 cells as the first and the last don't change, 2 states - 0 or 1)
N = (N%14==0)?14:N%14;
for(int i=0;i<N;i++){
vector<int> tmp(8,0);
for(int j=1;j<7;j++){
// cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0
// cells and cells are always 0
tmp[j]=(cells[j-1]==cells[j+1])?1:0;
}
cells=tmp;
}
return cells;
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

### Discussion   