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 :slight_smile:

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… :slightly_frowning_face:
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 :neutral_face:. So, i want to know whether there is any other shortcut solution :slight_smile:

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
bad_permut=1
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:
values.append(((i-1)*values[i-1])+bad_permut)
bad_permut=(i-1)*values[i-1]
def compute():

for _ in range(int(input())):
    n=int(stdin.readline())
    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