Given two positive integers N (N>1) and K, the task is to output such permutation and the minimum value of Z/K, considering the below conditions:
- A[ i ] ≠ i for (1 <= i <= N)
- Value of Z/K is minimized, Where Z = ∑A[ i ] % i for (1 <= i <= N)
Examples:
Input: N = 2, K = 1
Output: Permutation: 2 1
Minimum Z/K = 1
Explanation: The permutation of size 2 is [2, 1] where no element is equal to its index, Which gives Z as ( 2 % 1) + (1 % 2) = 0 + 1 = 1. The value of Z/K = will be 1, Which is the minimum possible.Input: N = 3, K = 5
Output: Permutation: 2 3 1
Minimum Z/K = 0
Explanation: It can be verified that the value of Z/K is the minimum possible, and the permutation follows all the given conditions.
Approach: Follow the idea given below to solve the problem
The problem is observation based and can be solved by using those observations. For more clarification see the Concept of approach section.
Concept of approach:
We have to minimize the value of Z/K, Where Z = ∑A[ i ] % i for (1 <= i <= N). Value Z/K will minimized only and only if Z is the minimum possible. For making Z a possible minimum, The permutation can be created by following below steps:
- Create an array of N elements from 1 to N.
- Left rotate the whole array once in a circular manner by assuming that the array is circularly connected.
- After this operation, there will no index in permutation such that A[ i ] == i, and the value of Z will also be minimized.
Example:
N = 5, Array = {1, 2, 3, 4, 5}, Left rotated Array = {2, 3, 4, 5, 1}
Value of Z for array = (A[ 1 ] % 1 ) + (A[ 2 ] % 2 ) + (A[ 3 ] % 3 ) + (A[ 4 ] % 4 ) + (A[ 5 ] % 5 ) = (2 % 1) + (3 % 2) + (4 % 3) + (5%4) + (1 % 5) = 0+1+1+1+1 = 4. Which is the minimum possible value of Z. Then just output the value of Z/K along with the permutation. Formally, for any value of N (N>1) the minimum value of Z/K will be ( N – 1 )/K. Because the steps described for creating permutation will always give the value of Z = N-1, Which is the minimum possible.
Steps were taken to solve the problem:
- For creating permutation:
- Run a loop from i = 2 to i<=N and print the value of i for each iteration.
- Print 1 after executing the loop successfully.
- For the minimum value of Z/K:
- Print the value of (N-1)/K.
Below is the code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Method for printing permutation // and min value of Z/K void minZ( int N, int K) { for ( int i = 2; i <= N; i++) { cout << i << " " ; } cout << 1 << endl; cout<< (N - 1) / K << endl; } int main() { // Inputs int N = 3; int K = 5; // function call minZ(N, K); } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Driver Function public static void main(String[] args) throws java.lang.Exception { // Inputs int N = 3 ; int K = 5 ; // function call minZ(N, K); } // Method for printing permutation // and min value of Z/K static void minZ( int N, int K) { for ( int i = 2 ; i <= N; i++) { System.out.print(i + " " ); } System.out.println( 1 ); System.out.println((N - 1 ) / K); } } |
Python3
#GFG # Python program to implement the approach # Method for printing permutation # and min value of Z/K def minZ(N, K): # Printing the permutation for i in range ( 2 , N + 1 ): print (i, end = " " ) print ( 1 ) # Calculating the minimum value of Z/K print ((N - 1 ) / / K) # Driver Function if __name__ = = "__main__" : # Inputs N = 3 K = 5 # function call minZ(N, K) # This code is written by Sundaram |
C#
// C# code to implement the approach using System; public class GFG{ // Method for printing permutation // and min value of Z/K static void minZ( int N, int K) { for ( int i = 2; i <= N; i++) { Console.Write(i + " " ); } Console.WriteLine(1); Console.WriteLine((N - 1) / K); } // Driver Function static public void Main (){ // Inputs int N = 3; int K = 5; // function call minZ(N, K); } } |
Javascript
// JavaScript code to implement the approach // Method for printing permutation // and min value of Z/K function minZ(N, K){ let permutation = "" ; for (let i = 2; i <= N; i++) { permutation += i + " " ; } permutation += 1; // Printing the permutation console.log(permutation); // Calculating the minimum value of Z/K console.log(Math.floor((N - 1) / K)); } // Inputs let N = 3; let K = 5; // function call minZ(N, K); |
2 3 1 0
Time Complexity: O(N)
Auxiliary Space: O(1)