We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Construct the Array
Construct the Array
Sort by
recency
|
170 Discussions
|
Please Login in order to post a comment
This problem required very little memoization. I noticed a pattern; consider the number of arrays of length 2: [0,1,1] where index is the ending number x. Using a dynamic coding strategy, you might try to find the number of arrays of length 3 by summing up elements of this array: [2,1,1] You don't add the number of arrays of length 2 ending in the same x, since the numbers can't appear twice in a row. Therefore, index 1 is one greater, since it ignored the one element that was 1 less than the others. Using this array, the number of arrays of length 4 is: [2,3,3] This time, index 1 is one less since it ignored the one element that was one more than the rest. The pattern continues: [6,5,5] [10,11,11]
So we can ditch using arrays and just consider the number of arrays ending in x>1. The number N(n) of arrays of length n ending in x>1 is equal to (k-1)*N(n-1) + (1 if n is even, -1 if n is odd)
if x==1, subtract 1 if n is even, add 1 if n is odd
Did not understand why my code passed only first 2 testcases and failed all the rest until I realized that the modulo code was not in the right place.
If you comment your modulo code and it passes the testcases below when n<12 but will fail as soon as n=12 , then your code is very close to the solution.
10 10 2 38742049
11 10 2 348678440
12 10 2 138105940
how to avoid recursion:
how to avoid recusrion?
!/bin/python3
import math import os import random import re import sys
#
Complete the 'countArray' function below.
#
The function is expected to return a LONG_INTEGER.
The function accepts following parameters:
1. INTEGER n
2. INTEGER k
3. INTEGER x
#
def _build_dp(last, s, array, rest, x, n): if len(rest)>n: return 0 if n==2: if s!=x: return 1 else: return 0
_count=0 if (len(rest)==n): for i in rest: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) else: for i in array: if i!=s: _count+=_build_dp(s, i, array, [ j for j in rest if j!=i ], x, n-1) return _count
def countArray(n, k, x): _count=0 for i in range(2, k+1): _count+=_build_dp(1, i, range(1, k+1), [ i for i in range(2, k+1) if i!=x], x, n-1) return _count
if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')