PPERM: Doubt regarding logic

general
, , ,
1

I’m a newbie in dynamic programming. I saw this question: http://www.codechef.com/problems/PPERM

And when I read the editorial (link), I was a bit confused at this statement: pperm1 = 1

Why have we initialised pperm1 as 1? Shouldn’t pperm1 be n? Because if any number from 1 to n is placed in the 1st position then the condition is satisfied since that number will always be smallest of the 1st ‘1’ numbers according to the question. I’m just a beginner so if I’m wrong, then please correct me :slight_smile:

1 Like
2

In question read carefully that "A permutation of N distinct integers between 1 and N" is required

So if we are filling pperm[1], it means that you have to construct the permutation of length 1 only so you only have choice as 1, thus we put pperm[1] = 1

Also the value of pperm[] array is independent of the value of 'N’

Happy Coding :slight_smile:

1 Like