HackerRank Construct the Array Problem Solution

In this post, we will solve 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 a.
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 109 +7.
For example, for n = 4. k=3, x=2, there are 3 ways, as shown here:

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

Sample Input
n = 4. k=3. x = 2
Sample Output
3
Explanation
Refer to the diagram in the challenge statement.

HackerRank Construct the Array Problem Solution

Construct the Array C Solution

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

const int MOD = 1e9+7;
long int countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    long long res = k-1;
    for (int i = 4; i <= n; i++) {
        res = ((res + (i&1 ? 1 : -1))*(k-1))%MOD;
    }
    if (x != 1) res += (n&1 ? -1 : 1);
    
    return (res%MOD+MOD)%MOD;
}

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

Construct the Array C++ Solution

//Priyanshu Kumar : IIIT Allahabad
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define MAX 100005
#define MOD 1000000007
#define sz size()
#define ln length()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define pin(n) printf("%d\n",n);
#define pl(n) printf("%lld",n)
#define pln(n) printf("%lld\n",n);
#define FUCK_YEAH ios_base::sync_with_stdio(false);cin.tie(NULL)
inline ll gcd(ll x,ll y){return x%y==0?y:gcd(y,x%y);}
inline ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
inline ll powmod(ll a,ll b,ll mod) 
{
	ll res=1;
	a%=mod; 
	assert(b>=0); 
	for(;b;b>>=1)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
inline ll mulmod(ll a, ll b, ll c)
{
	if(!b)return 0;
	ll x = mulmod(a, b/2, c);
	if (b & 1)return (x+x+a)%c;
	return (x+x)%c;
}

int main()
{
	FUCK_YEAH;
	ll n,k,x;
	cin >> n >> k >> x;
	ll dp[n][2];
	dp[0][0] = 0;
	dp[0][1] = 1;
	for(int i=1;i<n-2;i++) {
		dp[i][0] = (powmod(k-1,i,MOD) - dp[i-1][0] + MOD)%MOD;
		dp[i][1] = (powmod(k-1,i,MOD) - dp[i-1][1] + MOD)%MOD;
	}
	ll ans = 0;
	for(int i=1;i<=k;i++) {
		if(x != i) {
			if(i == 1) {
				ans = (ans + dp[n-3][0])%MOD;
			}
			else {
				ans = (ans + dp[n-3][1])%MOD;
			}
		}
	}
	cout << ans <<endl;
	return 0;
}

Construct the Array C Sharp Solution

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading;
using static System.Array;
using static System.Math;
using System.Reflection;

partial class Solution
{
#if CSHARP7
    long CountArray(int n, long k, long x)
    {
        if (n == 3)
            return x == 1 ? k - 1 : k - 2;

        long result = dp[n, x==1 ? 0 : 1];
        if (result != 0) return result;

        if (x == 1)
        {
            result = ((k - 1) * CountArray(n - 1, k, 2) % MOD);
        }
        else
        {
            result = ((k - 2) * CountArray(n - 1, k, 2) % MOD
                         + CountArray(n - 1, k, 1) % MOD);
        }

        dp[n, x == 1 ? 0 : 1] = Fix(result);
        return result;
    }

    private long[,] dp = new long[100001, 2];


    void Solve()
    {
        int n = Ni();
        int k = Ni();
        int x = Ni();
        long answer = CountArray(n, k, x);
        WriteLine(Fix(answer));
    }

    #region Mod Math
    public const int MOD = 1000000007;
    const int FactCache = 1000;

    static int[] _inverse;
    public static long Inverse(long n)
    {
        long result;

        if (_inverse == null)
            _inverse = new int[3000];

        if (n < _inverse.Length && (result = _inverse[n]) != 0)
            return result - 1;

        result = ModPow(n, MOD - 2);
        if (n < _inverse.Length)
            _inverse[n] = (int)(result + 1);
        return result;
    }

    public static long Mult(long left, long right) =>
        (left * right) % MOD;

    public static long Div(long left, long divisor) =>
        left * Inverse(divisor) % MOD;

    public static long Add(long x, long y) =>
        (x += y) >= MOD ? x - MOD : x;

    public static long Subtract(long x, long y) => (x -= y) < 0 ? x + MOD : x;

    public static long Fix(long n) => (n %= MOD) >= 0 ? n : n + MOD;

    public static long ModPow(long n, long p, long mod = MOD)
    {
        long b = n;
        long result = 1;
        while (p != 0)
        {
            if ((p & 1) != 0)
                result = (result * b) % mod;
            p >>= 1;
            b = (b * b) % mod;
        }
        return result;
    }

    static List<long> _fact, _ifact;

    public static long Fact(int n)
    {
        if (_fact == null) _fact = new List<long>(FactCache) { 1 };
        for (int i = _fact.Count; i <= n; i++)
            _fact.Add(Mult(_fact[i - 1], i));
        return _fact[n];
    }

    public static long InverseFact(int n)
    {
        if (_ifact == null) _ifact = new List<long>(FactCache) { 1 };
        for (int i = _ifact.Count; i <= n; i++)
            _ifact.Add(Div(_ifact[i - 1], i));
        return _ifact[n];
    }

    public static long Fact(int n, int m)
    {
        var fact = Fact(n);
        if (m < n) fact = fact * InverseFact(n - m) % MOD;
        return fact;
    }

    public static long Comb(int n, int k)
    {
        if (k <= 1) return k == 1 ? n : k == 0 ? 1 : 0;
        return Mult(Mult(Fact(n), InverseFact(k)), InverseFact(n - k));
    }
    #endregion

    #region Common
    public static void Swap<T>(ref T a, ref T b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }

    public static void Clear<T>(T[] t, T value = default(T))
    {
        for (int i = 0; i < t.Length; i++)
            t[i] = value;
    }

    public static V Get<K, V>(Dictionary<K, V> dict, K key) where V : new()
    {
        V result;
        if (dict.TryGetValue(key, out result) == false)
            result = dict[key] = new V();
        return result;
    }

    public static int Bound<T>(T[] array, T value, bool upper = false)
        where T : IComparable<T>
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            int cmp = value.CompareTo(array[mid]);
            if (cmp > 0 || cmp == 0 && upper)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    public static long IntPow(long n, long p)
    {
        long b = n;
        long result = 1;
        while (p != 0)
        {
            if ((p & 1) != 0)
                result = (result * b);
            p >>= 1;
            b = (b * b);
        }
        return result;
    }

    public static int Log2(long value)
    {
        if (value <= 0)
            return value == 0 ? -1 : 63;

        var log = 0;
        if (value >= 0x100000000L)
        {
            log += 32;
            value >>= 32;
        }
        if (value >= 0x10000)
        {
            log += 16;
            value >>= 16;
        }
        if (value >= 0x100)
        {
            log += 8;
            value >>= 8;
        }
        if (value >= 0x10)
        {
            log += 4;
            value >>= 4;
        }
        if (value >= 0x4)
        {
            log += 2;
            value >>= 2;
        }
        if (value >= 0x2)
        {
            log += 1;
        }
        return log;
    }

    public static int BitCount(long x)
    {
        int count;
        var y = unchecked((ulong)x);
        for (count = 0; y != 0; count++)
            y &= y - 1;
        return count;
    }

    public static int HighestOneBit(int n) => n != 0 ? 1 << Log2(n) : 0;
    public static long HighestOneBit(long n) => n != 0 ? 1L << Log2(n) : 0;
    #endregion

    #region Fast IO
    #region  Input
    static System.IO.Stream inputStream;
    static int inputIndex, bytesRead;
    static byte[] inputBuffer;
    static System.Text.StringBuilder builder;
    const int MonoBufferSize = 4096;

    public static void InitInput(System.IO.Stream input = null, int stringCapacity = 16)
    {
        builder = new System.Text.StringBuilder(stringCapacity);
        inputStream = input ?? Console.OpenStandardInput();
        inputIndex = bytesRead = 0;
        inputBuffer = new byte[MonoBufferSize];
    }

    static void ReadMore()
    {
        if (bytesRead < 0) throw new FormatException();
        inputIndex = 0;
        bytesRead = inputStream.Read(inputBuffer, 0, inputBuffer.Length);
        if (bytesRead > 0) return;
        bytesRead = -1;
        inputBuffer[0] = (byte)'\n';
    }

    public static int Read()
    {
        if (inputIndex >= bytesRead) ReadMore();
        return inputBuffer[inputIndex++];
    }

    public static T[] N<T>(int n, Func<T> func)
    {
        var list = new T[n];
        for (int i = 0; i < n; i++) list[i] = func();
        return list;
    }

    public static int[] Ni(int n) => N(n, Ni);

    public static long[] Nl(int n) => N(n, Nl);

    public static string[] Ns(int n) => N(n, Ns);

    public static int Ni() => (int)Nl();

    public static long Nl()
    {
        var c = SkipSpaces();
        bool neg = c == '-';
        if (neg) { c = Read(); }

        long number = c - '0';
        while (true)
        {
            var d = Read() - '0';
            if (unchecked((uint)d > 9)) break;
            number = number * 10 + d;
            if (number < 0) throw new FormatException();
        }
        return neg ? -number : number;
    }

    public static char[] Nc(int n)
    {
        var list = new char[n];
        for (int i = 0, c = SkipSpaces(); i < n; i++, c = Read()) list[i] = (char)c;
        return list;
    }

    public static string Ns()
    {
        var c = SkipSpaces();
        builder.Clear();
        while (true)
        {
            if (unchecked((uint)c - 33 >= (127 - 33))) break;
            builder.Append((char)c);
            c = Read();
        }
        return builder.ToString();
    }

    public static int SkipSpaces()
    {
        int c;
        do c = Read(); while (unchecked((uint)c - 33 >= (127 - 33)));
        return c;
    }

    public static string ReadLine()
    {
        builder.Clear();
        while (true)
        {
            int c = Read();
            if (c < 32) { if (c == 10 || c <= 0) break; continue; }
            builder.Append((char)c);
        }
        return builder.ToString();
    }
    #endregion

    #region Output
    static System.IO.Stream outputStream;
    static byte[] outputBuffer;
    static int outputIndex;

    public static void InitOutput(System.IO.Stream output = null)
    {
        outputStream = output ?? Console.OpenStandardOutput();
        outputIndex = 0;
        outputBuffer = new byte[65535];
    }

    public static void WriteLine(object obj = null)
    {
        Write(obj);
        Write('\n');
    }

    public static void WriteLine(long number)
    {
        Write(number);
        Write('\n');
    }

    public static void Write(long signedNumber)
    {
        ulong number = unchecked((ulong)signedNumber);
        if (signedNumber < 0)
        {
            Write('-');
            number = unchecked((ulong)(-signedNumber));
        }

        Reserve(20 + 1); // 20 digits + 1 extra for sign
        int left = outputIndex;
        do
        {
            outputBuffer[outputIndex++] = (byte)('0' + number % 10);
            number /= 10;
        }
        while (number > 0);

        int right = outputIndex - 1;
        while (left < right)
        {
            byte tmp = outputBuffer[left];
            outputBuffer[left++] = outputBuffer[right];
            outputBuffer[right--] = tmp;
        }
    }

    public static void Write(object obj)
    {
        if (obj == null) return;

        var s = obj.ToString();
        Reserve(s.Length);
        for (int i = 0; i < s.Length; i++)
            outputBuffer[outputIndex++] = (byte)s[i];
    }

    public static void Write(char c)
    {
        Reserve(1);
        outputBuffer[outputIndex++] = (byte)c;
    }

    public static void Write(byte[] array, int count)
    {
        Reserve(count);
        Array.Copy(array, 0, outputBuffer, outputIndex, count);
        outputIndex += count;
    }

    static void Reserve(int n)
    {
        if (outputIndex + n <= outputBuffer.Length)
            return;

        Dump();
        if (n > outputBuffer.Length)
            Array.Resize(ref outputBuffer, Math.Max(outputBuffer.Length * 2, n));
    }

    static void Dump()
    {
        outputStream.Write(outputBuffer, 0, outputIndex);
        outputIndex = 0;
    }

    public static void Flush()
    {
        Dump();
        outputStream.Flush();
    }

    #endregion
    #endregion
#endif

    #region Main
    static void IncreaseStack(ThreadStart action, int stackSize = 16 * 1024 * 1024)
    {
        var thread = new Thread(action, stackSize);
#if __MonoCS__ 
        var f = BindingFlags.NonPublic | BindingFlags.Instance;
        var t = typeof(Thread).GetField("internal_thread", f).GetValue(thread);
		t.GetType().GetField("stack_size", f).SetValue(t, stackSize);
#endif
        thread.Start();
        thread.Join();
    }

    public static void Main(params string[] args)
    {
        AppDomain.CurrentDomain.UnhandledException += (sender, arg) =>
        {
            var e = (Exception)arg.ExceptionObject;
            Console.Error.WriteLine(e);
            var line = new StackTrace(e, true).GetFrames()
                .Select(x => x.GetFileLineNumber()).FirstOrDefault(x => x != 0);
            var wait = line % 300 * 10 + 5;
            var process = Process.GetCurrentProcess();
            while (process.TotalProcessorTime.TotalMilliseconds > wait && wait < 3000) wait += 1000;
            while (process.TotalProcessorTime.TotalMilliseconds < Math.Min(wait, 3000)) ;
            Environment.Exit(1);
        };

#if CSHARP7
        InitInput(Console.OpenStandardInput());
        InitOutput(Console.OpenStandardOutput());
        IncreaseStack(()=>new Solution().Solve());
        Flush();
        Console.Error.WriteLine(Process.GetCurrentProcess().TotalProcessorTime);
#else
        Process.Start("sh", "-c \"mono-csc -d:CSHARP7 -debug -o+ -unsafe solution.cs >&2; mono --debug solution.exe\"")
            ?.WaitForExit();
#endif
    }
    #endregion
}

Construct the Array Java Solution

import java.util.Locale;
import java.util.Scanner;

public class ConstructTheArray {

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            in.useLocale(Locale.ENGLISH);
            int n = in.nextInt();
            int k = in.nextInt();
            int x = in.nextInt();
            long a = 0;
            long b = 1;

            for (int i = 3; i <= n; i++) {
                long a2 = (k - 1) * b;
                a2 %= Constants.MODULUS;
                long b2 = (k - 2) * b;
                b2 %= Constants.MODULUS;
                b2 += a;
                b2 %= Constants.MODULUS;
                a = a2;
                b = b2;
            }

            if (x == 1) {
                System.out.println(a);
            } else {
                System.out.println(b);
            }
        }
    }

    private static class Constants {
        public static final long MODULUS = 1000000007;
    }
}

Construct the Array Python Solution

#!/bin/python3

import sys

def countArray(n, k, x):
    # Return the number of ways to fill in the array.
    d, s = 1, 0
    for i in range(2, n):
        d, s = (k - 2) * d + s, (k - 1) * d
    return d if x != 1 else s

if __name__ == "__main__":
    n, k, x = input().strip().split(' ')
    n, k, x = [int(n), int(k), int(x)]
    answer = countArray(n, k, x)
    print(answer % (10 ** 9 + 7))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python