Dado un número N. La tarea es encontrar la permutación P de los primeros N números naturales tal que la suma de i % P i sea la máxima posible. La tarea es encontrar la suma máxima posible, no su permutación.
Ejemplos:
Entrada: N = 5
Salida: 10
La permutación posible es 2 3 4 5 1.
Los valores del módulo serán {1, 2, 3, 4, 0}.
1 + 2 + 3 + 4 + 0 = 10Entrada: N = 8
Salida: 28
Planteamiento: La suma máxima posible es (N * (N – 1)) / 2 y está formada por la permutación 2, 3, 4, 5, ….. N, 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the permutation of // the first N natural numbers such that // the sum of (i % Pi) is maximum possible // and return the maximum sum int Max_Sum(int n) { return (n * (n - 1)) / 2; } // Driver code int main() { int n = 8; // Function call cout << Max_Sum(n); return 0; }
Java
// Java implementation of the approach class GFG { // Function to find the permutation of // the first N natural numbers such that // the sum of (i % Pi) is maximum possible // and return the maximum sum static int Max_Sum(int n) { return (n * (n - 1)) / 2; } // Driver code public static void main (String[] args) { int n = 8; // Function call System.out.println(Max_Sum(n)); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to find the permutation of # the first N natural numbers such that # the sum of (i % Pi) is maximum possible # and return the maximum sum def Max_Sum(n) : return (n * (n - 1)) // 2; # Driver code if __name__ == "__main__" : n = 8; # Function call print(Max_Sum(n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // Function to find the permutation of // the first N natural numbers such that // the sum of (i % Pi) is maximum possible // and return the maximum sum static int Max_Sum(int n) { return (n * (n - 1)) / 2; } // Driver code public static void Main (String[] args) { int n = 8; // Function call Console.WriteLine(Max_Sum(n)); } } // This code is contributed by Princi Singh
Javascript
<script> // Javascript implementation of the approach // Function to find the permutation of // the first N natural numbers such that // the sum of (i % Pi) is maximum possible // and return the maximum sum function Max_Sum(n) { return parseInt((n * (n - 1)) / 2); } // Driver code let n = 8; // Function call document.write(Max_Sum(n)); // This code is contributed by rishavmahato348 </script>
28
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA