Find the permutation of first N natural numbers such that sum of i % Pi is maximum possible
Given a number N. The task is to find the permutation P of first N natural numbers such that sum of i % Pi is maximum possible. The task is to find the maximum possible sum not it’s permutation.
Examples:
Input: N = 5
Output: 10
Possible permutation is 2 3 4 5 1.
Modulus values will be {1, 2, 3, 4, 0}.
1 + 2 + 3 + 4 + 0 = 10Input: N = 8
Output: 28
Approach: Maximum possible sum is (N * (N – 1)) / 2 and it is formed by the permutation 2, 3, 4, 5, ….. N, 1.
Below is the implementation of the above approach:
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 import java.io.*; public 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> |
Output:
28
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us