Count of Arrays Having Consecutive Elements with Different Values in C++

Given three variables size, max_val, last_element as input. The goal is to find the count of different arrays that can be formed in a manner such that they have size elements, have elements between 1 and max_val and the first element is always 1 and the last element is always max_val. Also make sure that no two consecutive elements are the same.

Let us understand with examples.

For Example

Input - size = 5, max_val = 3, last_element = 3

Output - Count of arrays having consecutive element with different values are: 5

Explanation - The arrays will be:-

[ 1, 2, 3, 1, 3 ], [ 1, 2, 3, 2, 3 ], [ 1, 2, 1, 2, 3 ], [ 1, 3, 1, 2, 3 ], [ 1, 3, 2, 1, 3 ].

Input -  size = 3  max_val = 2   last_element = 2

Output - Count of arrays having consecutive element with different values are: 0

Explanation - No array possible with 3 elements and having [ 1, _, 2 ] as consecutive elements as we cannot fill anything except 1 or 2 for the middle element and this will violate consecutive different elements' condition.

Approach used in the below program is as follows

• In this approach we will use dynamic programming and combinatorics for finding such arrays count. 
• The first and last elements will be fixed as 1 and last_element. For any size of arrays the ways to fill it will be for size-2 elements only.
• For filling [1 to max_val] elements to be filled in size-2 places. Ways will be ways(max_val)= ways(size) / (max_val - 1) 
• For each range 1 to i, ways will be ways(i)=ways(size) / (max_val - 1) [  ways(size) = number of ways last element can be filled with numbers 2 to max_val ).
• If last_element is 1 then ways will be ways(size-1) as last element can only be 1.
• The second last element can always be between 1 and max_val.
• If second last element is not 1 then ways will be (max_val-2)*ways(i-1) as arr_icannot be 1 or arri-1</sub>
• If second last element is 1 then ways will be (max_val-1)*ways(i-1) as arr_i-1 is 1 and arr_i-2 is not 1.
• Ways(i) will be :- (max_val - 2)*ways(i-2) + (max_val-2)*ways(i-1)
• Take variables size, max_val and last_element as input.
• Function diff_val(int size, int max_val, int last_element) takes all inputs and returns the count of arrays having consecutive elements with different values.
• Take the initial count as 0.
• Take array arr[Max_N] = { 0 } storing count of ways to fill arrays. Initialize arr[0] with 0 and arr[1] with 1.
• Traverse from i=2 to i<size.
• Take temp_1 = (max_val - 2) * arr[i - 1] and temp_2 = (max_val - 1) * arr[i - 2]
• Set  arr[i] = temp_1 + temp_2.
• In case last_element == 1 then set count = (max_val - 1) * arr[size - 2].
• Otherwise return arr[size - 1].
• At the end return count as result.

Example

Live Demo

#include <bits/stdc++.h>
using namespace std;
#define Max_N 109

int diff_val(int size, int max_val, int last_element) {
   int count = 0;
   int arr[Max_N] = {
      0
   };
   arr[0] = 0;
   arr[1] = 1;
   for (int i = 2; i < size; i++) {
      int temp_1 = (max_val - 2) * arr[i - 1];
      int temp_2 = (max_val - 1) * arr[i - 2];
      arr[i] = temp_1 + temp_2;
   }
   if (last_element == 1) {
      count = (max_val - 1) * arr[size - 2];
   } else {
      return arr[size - 1];
   }
   return count;
}
int main() {
   int size = 5;
   int max_val = 3;
   int last_element = 3;
   cout << "Count of arrays having consecutive element with different values are: " << diff_val(size, max_val, last_element);
   return 0;
}

If we run the above code it will generate the following output −

Output

Count of arrays having consecutive element with different values are: 5