Dado un entero positivo N , la tarea es encontrar el número de permutaciones únicas de los primeros N números naturales que tienen la suma de los elementos adyacentes igual a un cuadrado perfecto .
Ejemplos:
Entrada: N = 17
Salida: 2
Explicación: Las
siguientes permutaciones tienen suma de elementos adyacentes igual a un cuadrado perfecto:
- {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}
Por lo tanto, la cuenta de tales permutaciones es 2.
Entrada: N = 13
Salida: 0
Enfoque: El problema dado se puede resolver usando los conceptos de Graph . Siga los pasos a continuación para resolver el problema:
- Enumera todos los números cuadrados perfectos hasta (2*N – 1) que se pueden obtener al sumar dos enteros positivos cualesquiera.
- Representa el gráfico como la representación de la lista de adyacencia, de modo que si la suma de dos números X e Y es un cuadrado perfecto, agrega un borde del Node X al Node Y.
- Cuente el número de Nodes en el gráfico cuyo grado de entrada sea 1 y guárdelo en una variable X .
- Ahora, el número de permutaciones se puede calcular según las siguientes condiciones:
- Si el valor de X es 0 , entonces son posibles un total de N permutaciones. Por lo tanto, imprima N como el resultado.
- Si el valor de X es 1 o 2 , entonces son posibles un total de 2 permutaciones. Por lo tanto, imprima 2 como resultado.
- De lo contrario, no existen tales permutaciones que satisfagan los criterios dados. Por lo tanto, imprima 0 como resultado.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA