Count permutations of first N natural numbers having sum of adjacent elements equal to a perfect square | 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 ; Count elements whose indegree is 1 ; Generate 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
function countPermutations ( N ) { let adj = [ ] ; for ( let i = 0 ; i < 105 ; i ++ ) adj . push ( [ ] ) ; let indeg = 0 ; for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = 1 ; j <= N ; j ++ ) { if ( i == j ) continue ; let sum = i + j ; if ( Math . ceil ( Math . sqrt ( sum ) ) == Math . floor ( Math . sqrt ( sum ) ) ) { adj [ i ] . push ( j ) ; } } if ( adj [ i ] . length == 1 ) indeg ++ ; } if ( indeg == 0 ) return N ; else if ( indeg <= 2 ) return 2 ; else return 0 ; } let N = 17 ; document . write ( countPermutations ( N ) ) ;