### PROBLEM LINK:

Practice

Contest

Video Editorial

**Author:** Dmytro Berezin

**Primary Tester** Prateek Gupta

**Editorialist:** Hussain Kara Fallah

### PROBLEM EXPLANATION

A rainbow array of **n** elements follows the form

**{** **1** (repeated **a _{1}** times),

**2**(

**a**times),

_{2}**3**(

**a**times),

_{3}**4**(

**a**times),

_{4}**5**(

**a**times),

_{5}**6**(

**a**times),

_{6}**7**(

**a**times),

_{7}**6**(

**a**times),

_{6}**5**(

**a**times),

_{5}**4**(

**a**times),

_{4}**3**(

**a**times),

_{3}**2**(

**a**times),

_{2}**1**(

**a**times)

_{1}**}**

2*(a_1+a_2+a_3+a_4+a_5+a_6)+a_7 = n

Given an array consisting of **n** elements, check if it’s a rainbow array or not.

### DIFFICULTY:

cakewalk

### PREREQUISITES:

None

### EXPLANATION:

This problem is similar to checking if a given string is a palindrome or not. The simplest and most effective way to check if the array is rainbow, is by maintaining 2 pointers one iterating through elements starting from the beginning of our array, and the other one iterating through the elements in the reversed direction.

Both of the first and the last element of the array must be ones. In fact, there must be two blocks consisting of the same number of **consecutive** ones **(1)** one of them located at the beginning of the array, and the other one at the end.

Figuring out the number of consecutive ones at the beginning of our array can be done easily by moving our first pointer forward, and stopping when encountering a number not equal to 1 or reaching the end of our array. We can do the same on the other side by moving our second pointer backwards. After that, we should check that we had processed the same number of **ones** on both sides.

After processing elements equal to **one**, you can observe that we are still solving the same problem (in fact, it’s a subproblem now). Both of our pointers must be referring to elements equal to **2**. Moving our pointers is equivalent to dropping elements, so if we consider that we have dropped processed **ones**, there must be two blocks consisting of the same number of **consecutive** twos **(2)** one of them located at the beginning of the array, and the other one at the end. Of course instead of using 2 pointers, maintaining a data structure which supports dropping elements from both ends of the array (Like C++ Deque) does the job perfectly.

After repeating the same procedure for **{1,2,3,4,5,6}** (considering that none of our conditions was violated, in case that happened we can report that our array is not rainbow and break) we would be finishing with a single block consisting **only** of elements equal to seven **7**. Reaching this point confirms that our array is rainbow.

You can check my implementation for better understanding.

### AUTHOR’S AND TESTER’S SOLUTIONS:

**AUTHOR’s solution**: Can be found here

**TESTER’s solution**: Can be found here

**EDITORIALIST’s solution**: Can be found here