# Why Only Beat 97% ?

• Since the algorithm has a small finite limit of input 15 it is as simple as precompute values for N 1...15 and return them from a constant array. But that should be the fastest solution, but still I get a time execution of beating only 97%.

What are the optimizations employed by the rest 3 % ?

``````#shameless pre-computation
class Solution2(object):
pre = [0, 1, 2, 3,  8,  10,  36,  41,  132, 250, 700,  750,  4010,  4237,10680,  24679]

def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
if (N < len(Solution2.pre)):
#print ('N' , N)
return Solution2.pre[N]

# brute force - optimized backtracking
class Solution(object):
def __init__(self):
self.pre = {1: 1, 2: 2, 3: 3, 4: 8, 5: 10, 6: 36, 7: 41, 8: 132, 9: 250, 10: 700, 11: 750, 12: 4010, 13: 4237, 14: 10680, 15: 24679}

def countArrangement(self, N):
"""
:type N: int
:rtype: int
"""
if (N <= len(self.pre)):
#print ('N' , N)
return self.pre[N]
m = self.getMap(N)
used = set()
printable = []
result = [0]
self.generate(0, m, used, result, N, printable)
return result[0]

def getMap(self, N):
options = [[0]*(N+1) for i in range(N+1)]
for i in range(1, N+1):
r  = i
while (r <= N) :
options[i][r] = 1
options[r][i] = 1
r+=i
#print (options)
result = [[j for j in range(len(i)) if i[j] ] for i in options]
result = result[1:]
#print (result)
return result

def generate(self, level, m, used, result, N, printable):
if level == N :
result[0] = result[0]+1
#print ('result', printable, used, result)
else:
for v in m[level]:
if v > N :
return
else:
if v not in used: