# Doubt regarding Permutations

Hey , i have a doubt regarding permutations . In some problems , we have to remove certain value from total permutations to get the resultant answer ( Example : permutations of string such that no two characters stay together ) . Theoritically , we solve such problems by removing the unnecessary permutations from the total number of permutations . But calculating the total permutations answer is impossible while writing code as the number can be very large . Can anyone please suggest me some approaches or resources to tackle such questions

isnâ€™t that just optimisation in short?
Like suppose we do Best First Search, we avoid unnecessary permutations by checking the cost to reach the global optimum answerâ€¦

1 Like

Yeah , but this is a bit different

Hereâ€™s the problem

Canâ€™t think of anything else besides a brute force approachâ€¦
I guess thereâ€™s a pattern.
Like 9 has [1,3,9] and 4 has [1,2,4]
they both will have the same answerâ€¦

I did solve the problem . There is a reccurrence relation . It took me around 3 hours to crack logic . So, i want to know whether there is any other shortcut solution

Code

from sys import stdin,stdout
from math import sqrt
def factor(n):
low=1
fact=0
high=sqrt(n)
while low<=high:
if n%low==0:
if n//low==high:
fact+=1
else:
fact+=2
low+=1
return fact
values=[]
for i in range(0,70):
if i==0:
values.append(0)
elif i==1:
values.append(0)
elif i==2:
values.append(1)
else:
def compute():

``````for _ in range(int(input())):
x=factor(n)
stdout.write(str(values[x]))
print()
``````

if name==â€śmainâ€ť:
compute()

This will give TLE?
And is my theory correct or wrong?

Brute force didnâ€™t work because the solution is bound to be recursive in nature

1 Like

was wondering the same thing

this is the program for the above question:

import math
import sys
sys.setrecursionlimit(1500)

dp = {}

def getDivisorCount(n):
rootN = int(math.sqrt(n))
divisors = []
for num in range(1, rootN + 1):
if(n % num == 0):
a = int(n / num)
if a * a == n:
divisors.append(a)
else:
divisors.append(num)
divisors.append(a)

``````return len(divisors)
``````

def validPermutation(n):
if(n == 1):
return 1
if(n == 2):
return 1
if(n == 3):
return 3
ans = 0
if n - 1 in dp:
ans += dp[n - 1]
else:
dp[n - 1] = (n - 1) * validPermutation(n - 1)
ans += dp[n - 1]
if n - 2 in dp:
ans += dp[n - 2]
else:
dp[n - 2] = (n - 2) * validPermutation(n - 2)
ans += dp[n - 2]
dp[n] = ans
return ans

t = int(input())
for _ in range(t):
n = int(input())
divisorCount = getDivisorCount(n)
print(validPermutation(divisorCount))