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
n
elements in the array, I have twofor
loops and it seems like an*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
yield
and I actually got this part of the solution from another SO post. I just want to know, have I usedyield
efficiently? What time/efficiency difference would it have made if I didn't useyield
in this case and just made a listperm_lst
then 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[0])) and (not(arr_after) or arr_after[0] != arr[0]):
yield perm[:i] + [arr[0]] + 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)