HackerRank Construct the Array problem solution

In this HackerRank Construct the Array problem solution your goal is to find the number of ways to construct an array such that consecutive positions contain different values.

Specifically, we want to construct an array with n elements such that each element between 1 and k, inclusive. We also want the first and last elements of the array to be 1 and x.

Given n, k and x, find the number of ways to construct such an array. Since the answer may be large, only find it modulo 10⁹ + 7.

Complete the function countArray which takes input n, k and x. Return the number of ways to construct the array such that consecutive elements are distinct.

HackerRank Construct the Array problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the countArray function below.
def countArray(n, k, x):
    # Return the number of ways to fill in the array.
    if x != 1:
        endx = 0
        end = 1
    else:
        endx = 1
        end =0
    for i in range(2,n+1):
        endx, end = end, (end*(k-2) +endx*(k-1))%(1000000000+7)
    return endx%(1000000000+7)
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nkx = input().split()

    n = int(nkx[0])

    k = int(nkx[1])

    x = int(nkx[2])

    answer = countArray(n, k, x)

    fptr.write(str(answer) + 'n')

    fptr.close()

Construct the Array problem solution in Java.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static long countArray(int n, int k, int x) {
        long dp[][] = new long[n][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        for (int i=1;i<n;i++) {
            dp[i][0] = (dp[i-1][1] * (k-1)) % 1000000007;
            dp[i][1] = (dp[i-1][0] + dp[i-1][1] * (k-2)) % 1000000007;
        }
        if (x == 1) {
            return dp[n-1][0];
        } else {
            return dp[n-1][1];
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int x = in.nextInt();
        long answer = countArray(n, k, x);
        System.out.println(answer);
        in.close();
    }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

void print(long arr[2][2]) {
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      cout << i << ' ' << j << ' ' << arr[i][j] << endl;
    }
  }
}

long countArray(int n, int k, int x) {
  long ways[2][2];
  ways[0][0] = 1;
  ways[0][1] = 0;
  bool fillSecond = true;
  for (int i = 0; i < n-1; i++) {
    ways[fillSecond][0] = (ways[!fillSecond][1] * (k - 1)) %  MOD;
    ways[fillSecond][1] = (ways[!fillSecond][1] * (k - 2) + ways[!fillSecond][0]) % MOD;
    fillSecond = !fillSecond;
  }
  
  long answer;
  if (x == 1) {
    answer = (ways[fillSecond][1] * (k - 1)) % MOD;
  }
  else {
    answer = (ways[fillSecond][1] * (k - 2) + ways[fillSecond][0]) % MOD;
  }
  return answer;
}

int main() {
    int n;
    int k;
    int x;
    cin >> n >> k >> x;
    long answer = countArray(n, k, x);
    cout << answer << endl;
    return 0;
}

Problem solution in C.

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <inttypes.h>

long int countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    int64_t MOD=1e9+7;
    int64_t eq_x = 0;
    int64_t neq_x = 0;
    if (x == 1) {
        eq_x = 1;
        neq_x = 0;
    } else {
        eq_x = 0;
        neq_x = 1;
    }
    for (int i = 1; i < n; i++) {
        int64_t eq_x1 = neq_x;
        int64_t neq_x1 = (k-1) * eq_x + (k-2) * neq_x;

        eq_x = eq_x1 % MOD;
        neq_x = neq_x1 % MOD;
    }
    return eq_x;
}

int main() {
    int n; 
    int k; 
    int x; 
    scanf("%i %i %i", &n, &k, &x);
    long int answer = countArray(n, k, x);
    printf("%ldn", answer);
    return 0;
}