Given an integer N, the task is to find a permutation of the integers from 1 to N such that 
is maximum.
Examples:
Input: N = 3 Output: 3 1 2 Sum of the remainder values is (0 + 1 + 2) = 3 which is the maximum possible.
Input: N = 5 Output: 5 1 2 3 4
Approach:
As it is known that the maximum value of a number X after doing the mod with Y is Y-1. The permutation that will yield the maximum sum of the modulus values will be {N, 1, 2, 3, …., N – 1}. After evaluating the expression 
on the above array the output array will be {0, 1, 2, 3, …., N – 1} and this is the maximum value that can be obtained.
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 vector<int> Findpermutation(int n) { vector<int> a(n + 1); // Put n at the first index 1 a[1] = n; // Put all the numbers from // 2 to n sequentially for (int i = 2; i <= n; i++) a[i] = i - 1; return a; } // Driver code int main() { int n = 8; vector<int> v = Findpermutation(n); // Display the permutation for (int i = 1; i <= n; i++) cout << v[i] << ' '; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to find the permutation static int[] Findpermutation(int n) { int [] a = new int[n + 1]; // Put n at the first index 1 a[1] = n; // Put all the numbers from // 2 to n sequentially for (int i = 2; i <= n; i++) a[i] = i - 1; return a; } // Driver code public static void main(String[] args) { int n = 8; int []v = Findpermutation(n); // Display the permutation for (int i = 1; i <= n; i++) System.out.print(v[i] + " "); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function to find the permutation def Findpermutation(n) : a = [0] * (n + 1); # Put n at the first index 1 a[1] = n; # Put all the numbers from # 2 to n sequentially for i in range(2, n + 1) : a[i] = i - 1; return a; # Driver code if __name__ == "__main__" : n = 8; v = Findpermutation(n); # Display the permutation for i in range(1, n + 1) : print(v[i], end = ' '); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { // Function to find the permutation static int[] Findpermutation(int n) { int [] a = new int[n + 1]; // Put n at the first index 1 a[1] = n; // Put all the numbers from // 2 to n sequentially for (int i = 2; i <= n; i++) a[i] = i - 1; return a; } // Driver code public static void Main(String[] args) { int n = 8; int []v = Findpermutation(n); // Display the permutation for (int i = 1; i <= n; i++) Console.Write(v[i] + " "); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to find the permutation function Findpermutation(n) { let a = new Array(n + 1); // Put n at the first index 1 a[1] = n; // Put all the numbers from // 2 to n sequentially for (let i = 2; i <= n; i++) a[i] = i - 1; return a; } // Driver code let n = 8; let v = Findpermutation(n); // Display the permutation for (let i = 1; i <= n; i++) document.write(v[i] + ' '); </script> |
Output:
8 1 2 3 4 5 6 7
Time Complexity: O(N), Space Complexity: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
