Count permutations of first N natural numbers having sum of adjacent elements equal to a perfect square
Given a positive integer N, the task is to find the number of unique permutations of first N natural numbers having sum of the adjacent elements equal to a perfect square.
Examples:
Input: N = 17
Output: 2
Explanation:
Following permutations have sum of adjacent elements equal to a perfect square:
- {17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16}
- {16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17}
Therefore, count of such permutations is 2.
Input: N = 13
Output: 0
Approach: The given problem can be solved by using the concepts of Graph. Follow the steps below to solve the problem:
- List all the perfect square numbers up to (2*N – 1) that can be obtained by adding any two positive integers.
- Represent the graph as the adjacency list representation such that if the sum of two numbers X and Y is a perfect square, then add an edge from node X to node Y.
- Count the number of nodes in the graph whose in-degree is 1 and store it in a variable X.
- Now, the number of permutation can be calculated as per the following conditions:
- If the value of X is 0, then a total of N permutations are possible. Hence, print N as the result.
- If the value of X is 1 or 2, then a total of 2 permutations are possible. Hence, print 2 as the result.
- Otherwise, no such permutations exist satisfying the given criteria. Hence, print 0 as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count total number of // permutation of the first N natural // number having the sum of adjacent // elements as perfect square int countPermutations( int N) { // Create an adjacency matrix vector<vector< int > > adj(105); // Count elements whose indegree // is 1 int indeg = 0; // Generate adjacency matrix for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= N; j++) { if (i == j) continue ; // Find the sum of i and j int sum = i + j; // If sum is perfect square. // then move from i to j if ( ceil ( sqrt (sum)) == floor ( sqrt (sum))) { // Add it in adjacency // list of i adj[i].push_back(j); } } // If any list is of size 1, // then the indegree is 1 if (adj[i].size() == 1) indeg++; } // If there is no element whose // indegree is 1, then N such // permutations are possible if (indeg == 0) return N; // If there is 1 or 2 elements // whose indegree is 1, then 2 // permutations are possible else if (indeg <= 2) return 2; // If there are more than 2 // elements whose indegree is // 1, then return 0 else return 0; } // Driver Code int main() { int N = 17; cout << countPermutations(N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; import java.lang.*; class GFG{ // Function to count total number of // permutation of the first N natural // number having the sum of adjacent // elements as perfect square static int countPermutations( int N) { // Create an adjacency matrix ArrayList< ArrayList<Integer>> adj = new ArrayList< ArrayList<Integer>>( 105 ); for ( int i = 0 ; i < 105 ; i++) adj.add( new ArrayList<Integer>()); // Count elements whose indegree // is 1 int indeg = 0 ; // Generate adjacency matrix for ( int i = 1 ; i <= N; i++) { for ( int j = 1 ; j <= N; j++) { if (i == j) continue ; // Find the sum of i and j int sum = i + j; // If sum is perfect square. // then move from i to j if (Math.ceil(Math.sqrt(sum)) == Math.floor(Math.sqrt(sum))) { // Add it in adjacency // list of i adj.get(i).add(j); } } // If any list is of size 1, // then the indegree is 1 if (adj.get(i).size() == 1 ) indeg++; } // If there is no element whose // indegree is 1, then N such // permutations are possible if (indeg == 0 ) return N; // If there is 1 or 2 elements // whose indegree is 1, then 2 // permutations are possible else if (indeg <= 2 ) return 2 ; // If there are more than 2 // elements whose indegree is // 1, then return 0 else return 0 ; } // Driver Code public static void main(String[] args) { int N = 17 ; System.out.println(countPermutations(N)); } } // This code is contributed by Dharanendra L V. |
Python3
# python program for the above approach from math import sqrt,floor,ceil # Function to count total number of # permutation of the first N natural # number having the sum of adjacent # elements as perfect square def countPermutations(N): # Create an adjacency matrix adj = [[] for i in range ( 105 )] # bCount elements whose indegree # bis 1 indeg = 0 # bGenerate adjacency matrix for i in range ( 1 , N + 1 ): for j in range ( 1 , N + 1 ): if (i = = j): continue # Find the sum of i and j sum = i + j # If sum is perfect square. # then move from i to j if (ceil(sqrt( sum )) = = floor(sqrt( sum ))): # Add it in adjacency # list of i adj[i].append(j) # If any list is of size 1, # then the indegree is 1 if ( len (adj[i]) = = 1 ): indeg + = 1 # If there is no element whose # indegree is 1, then N such # permutations are possible if (indeg = = 0 ): return N # If there is 1 or 2 elements # whose indegree is 1, then 2 # permutations are possible elif (indeg < = 2 ): return 2 # If there are more than 2 # elements whose indegree is # 1, then return 0 else : return 0 # Driver Code if __name__ = = '__main__' : N = 17 print (countPermutations(N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to count total number of // permutation of the first N natural // number having the sum of adjacent // elements as perfect square static int countPermutations( int N) { // Create an adjacency matrix List<List< int >> adj = new List<List< int >>(105); for ( int i = 0; i < 105; i++) adj.Add( new List< int >()); // Count elements whose indegree // is 1 int indeg = 0; // Generate adjacency matrix for ( int i = 1; i <= N; i++) { for ( int j = 1; j <= N; j++) { if (i == j) continue ; // Find the sum of i and j int sum = i + j; // If sum is perfect square. // then move from i to j if (Math.Ceiling(Math.Sqrt(sum)) == Math.Floor(Math.Sqrt(sum))) { // Add it in adjacency // list of i adj[i].Add(j); } } // If any list is of size 1, // then the indegree is 1 if (adj[i].Count == 1) indeg++; } // If there is no element whose // indegree is 1, then N such // permutations are possible if (indeg == 0) return N; // If there is 1 or 2 elements // whose indegree is 1, then 2 // permutations are possible else if (indeg <= 2) return 2; // If there are more than 2 // elements whose indegree is // 1, then return 0 else return 0; } // Driver Code public static void Main() { int N = 17; Console.WriteLine(countPermutations(N)); } } // This code is contributed by SoumikMondal |
Javascript
<script> // JavaScript 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 function countPermutations(N) { // Create an adjacency matrix let adj = []; for (let i = 0; i < 105; i++) adj.push([]); // Count elements whose indegree // is 1 let indeg = 0; // Generate adjacency matrix for (let i = 1; i <= N; i++) { for (let j = 1; j <= N; j++) { if (i == j) continue ; // Find the sum of i and j let sum = i + j; // If sum is perfect square. // then move from i to j if (Math.ceil(Math.sqrt(sum)) == Math.floor(Math.sqrt(sum))) { // Add it in adjacency // list of i adj[i].push(j); } } // If any list is of size 1, // then the indegree is 1 if (adj[i].length == 1) indeg++; } // If there is no element whose // indegree is 1, then N such // permutations are possible if (indeg == 0) return N; // If there is 1 or 2 elements // whose indegree is 1, then 2 // permutations are possible else if (indeg <= 2) return 2; // If there are more than 2 // elements whose indegree is // 1, then return 0 else return 0; } // Driver Code let N = 17; document.write(countPermutations(N)); // This code is contributed by patel2127 </script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(N2)