# 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

Thanks in advance 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))