SAMN- Editorial

Problem Link:- https://www.codechef.com/COSS2020/problems/SAMN

EDITORIAL:-

Difficulty - Easy-Medium.

Prerequisites - Prime number checking algorithm, mathematical knowledge of even and odd, array manipulation.

Explanation -

The question is tricky. If we try to start in the sequence of conditions checking given in the program then definitely the program will take a lot of time.

The set of numbers,that are made of N digits having each digit less than equal to N (except zero) is small than the set of prime numbers made of N digits.

Hence the sequence of checking the condition should be as follows,

Checking if the number starts with an even number and have odd numbers placed at the odd position. Also checking the repetition of digits in the number.

Checking the occurrence of the digits less than equal to N in the number, excluding zero.

Checking if the number a prime number.

For the first condition, we have to check if the number is starting with an even integer and there is no repetition of any digit in the number.

For the second condition, we have to check if the number consists of all digits from 1 to N.

For the last condition, we have to use the prime number checking algorithm to check if the number is a prime.

If a number satisfies the above condition we output it, else we output that no Samosa Number exists for that value of N.