I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank.
Here is the challenge. Given an array of integers, where each number can appear at most twice, count the number of permutations in which no identical numbers appear consecutively.
My solution solves the base test but not the others because it is too slow. That's okay for now (I find the actual solution difficult to understand, but I first would like feedback to my own solution).
My questions today are:
What is the time complexity of my algorithm? I have commented on what I am doing, best to start from the bottom up.
I think, given
nelements in the array, I have two
forloops and it seems like a
n*n!solution for one array, but I would really appreciate a clear explanation here on Big O for this particular piece of code.
I am new to Python's
yieldand I actually got this part of the solution from another SO post. I just want to know, have I used
yieldefficiently? What time/efficiency difference would it have made if I didn't use
yieldin this case and just made a list
perm_lstthen and there, to hold all unique permutations?
# Enter your code here. Read input from STDIN. Print output to STDOUT def getBeautifulPerms(arr, arrlen): if (arrlen==1): yield arr else: for perm in getBeautifulPerms(arr[1:], arrlen-1): for i in range(arrlen): arr_before = perm[:i] arr_after = perm[i:] if ( (not(arr_before) or arr_before[-1] != arr)) and (not(arr_after) or arr_after != arr): yield perm[:i] + [arr] + perm[i:] def printBeautifulPerms(arr, n): ''' @param arr array of integers (not null) @param n length of array arr post: prints the number of good permutations mod (10**9 + 7) ''' perm_lst =  for perm in getBeautifulPerms(arr, n): if perm not in perm_lst: perm_lst.append(perm) # remove duplicates print(len(perm_lst) % (10**9 + 7)) # main code - the problem states we'll receive this input: q = int(input()) # no of queries (arrays) for i in range(q): n = int(input()) # no of elements in array arr = input () # space separated array of n integers arr = arr.split() printBeautifulPerms(arr, n)