HackerRank Construct the Array problem solution

In this HackerRank Construct the Array problem solution we have given a number of elements present in the array and with k and x, we need to find the number of ways to construct such an array that each element between 1 and k is inclusive.

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()

{"mode":"full","isActive":false}

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();
    }
}

{"mode":"full","isActive":false}

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;
}

{"mode":"full","isActive":false}

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("%ld\n", answer);
    return 0;
}

{"mode":"full","isActive":false}