Count permutations of first N natural numbers having sum of adjacent elements equal to a perfect square | python program for the above approach ; Function to count total number of permutation of the first N natural number having the sum of adjacent elements as perfect square ; Create an adjacency matrix ; bCount elements whose indegree bis 1 ; bGenerate adjacency matrix ; Find the sum of i and j ; If sum is perfect square . then move from i to j ; Add it in adjacency list of i ; If any list is of size 1 , then the indegree is 1 ; If there is no element whose indegree is 1 , then N such permutations are possible ; If there is 1 or 2 elements whose indegree is 1 , then 2 permutations are possible ; If there are more than 2 elements whose indegree is 1 , then return 0 ; Driver Code
from math import sqrt , floor , ceil NEW_LINE def countPermutations ( N ) : NEW_LINE INDENT adj = [ [ ] for i in range ( 105 ) ] NEW_LINE indeg = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT for j in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT continue NEW_LINE DEDENT sum = i + j NEW_LINE if ( ceil ( sqrt ( sum ) ) == floor ( sqrt ( sum ) ) ) : NEW_LINE INDENT adj [ i ] . append ( j ) NEW_LINE DEDENT DEDENT if ( len ( adj [ i ] ) == 1 ) : NEW_LINE INDENT indeg += 1 NEW_LINE DEDENT DEDENT if ( indeg == 0 ) : NEW_LINE INDENT return N NEW_LINE DEDENT elif ( indeg <= 2 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT else : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 17 NEW_LINE print ( countPermutations ( N ) ) NEW_LINE DEDENT