Dados dos números enteros N y K , la tarea es encontrar el K -ésimo elemento en la permutación de los primeros N números naturales dispuestos de manera que todos los números pares aparezcan antes que los impares en orden creciente.
Ejemplos:
Entrada: N = 10, K = 3
Salida: 6
Explicación:
La permutación requerida es {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}.
El tercer número en la permutación es 6.Entrada: N = 5, K = 4
Salida: 3
Explicación:
La permutación requerida es {2, 4, 1, 3, 5}.
El cuarto número en la permutación es 3.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar la permutación requerida de los primeros N números naturales y luego atravesar la permutación para encontrar el K -ésimo elemento presente en ella.
Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos V[] de tamaño N , para almacenar la secuencia requerida.
- Inserta todos los números pares menores o iguales a N en V[] .
- Luego, inserte todos los números impares menores o iguales a N en V[] .
- Después de formar la array, imprima el valor de V[K – 1] 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 find the K-th element // in the required permutation void findKthElement(int N, int K) { // Stores the required permutation vector<int> v; // Insert all the even numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 == 0) { v.push_back(i); } } // Now, insert all odd numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 != 0) { v.push_back(i); } } // Print the Kth element cout << v[K - 1]; } // Driver Code int main() { int N = 10, K = 3; findKthElement(N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the K-th element // in the required permutation static void findKthElement(int N, int K) { // Stores the required permutation ArrayList<Integer> v = new ArrayList<>(); // Insert all the even numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 == 0) { v.add(i); } } // Now, insert all odd numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 != 0) { v.add(i); } } // Print the Kth element System.out.println(v.get(K - 1)); } // Driver code public static void main(String[] args) { int N = 10, K = 3; // functions call findKthElement(N, K); } } // This code is contributed by Kingash.
Python3
# python 3 program for the above approach # Function to find the K-th element # in the required permutation def findKthElement(N, K): # Stores the required permutation v = [] # Insert all the even numbers # less than or equal to N for i in range(1, N + 1): if (i % 2 == 0): v.append(i) # Now, insert all odd numbers # less than or equal to N for i in range(1, N + 1): if (i % 2 != 0): v.append(i) # Print the Kth element print(v[K - 1]) # Driver Code if __name__ == "__main__": N = 10 K = 3 findKthElement(N, K) # This code is contributed by ukasp.
C#
// C# program for above approach using System; using System.Collections.Generic; public class GFG { // Function to find the K-th element // in the required permutation static void findKthElement(int N, int K) { // Stores the required permutation List<int> v = new List<int>(); // Insert all the even numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 == 0) { v.Add(i); } } // Now, insert all odd numbers // less than or equal to N for (int i = 1; i <= N; i++) { if (i % 2 != 0) { v.Add(i); } } // Print the Kth element Console.WriteLine(v[K - 1]); } // Driver code public static void Main(String[] args) { int N = 10, K = 3; // functions call findKthElement(N, K); } } // This code is contributed by susmitakundugoaldanga.
Javascript
<script> // JavaScript program for the above approach // Function to find the K-th element // in the required permutation function findKthElement(N , K) { // Stores the required permutation var v = []; // Insert all the even numbers // less than or equal to N for (i = 1; i <= N; i++) { if (i % 2 == 0) { v.push(i); } } // Now, insert all odd numbers // less than or equal to N for (i = 1; i <= N; i++) { if (i % 2 != 0) { v.push(i); } } // Print the Kth element document.write(v[K - 1]); } // Driver code var N = 10, K = 3; // functions call findKthElement(N, K); // This code contributed by Rajput-Ji </script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la observación de que los primeros N/2 elementos son pares y el valor del K -ésimo elemento en la primera mitad es igual a K*2 . Si K > N/2 , el valor del K -ésimo elemento depende de si N es par o impar .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans, para almacenar el K -ésimo elemento.
- Compruebe si el valor de K ≤ N/2 . Si se determina que es cierto, actualice ans a K*2 .
- De lo contrario, K se encuentra en la segunda mitad. En este caso, ans depende del valor de N.
- Si el valor de N es par , actualice ans a (K*2)-N-1 .
- De lo contrario, actualice ans a (K*2)-N .
- Imprime el valor de ans 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 find the Kth element // in the required permutation void findKthElement(int N, int K) { // Store the required result int ans = 0; // If K is in the first // N / 2 elements, print K * 2 if (K <= N / 2) { ans = K * 2; } // Otherwise, K is greater than N/2 else { // If N is even if (N % 2 == 0) { ans = (K * 2) - N - 1; } // If N is odd else { ans = (K * 2) - N; } } // Print the required result cout << ans; } // Driver Code int main() { int N = 10, K = 3; findKthElement(N, K); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to find the Kth element // in the required permutation static void findKthElement(int N, int K) { // Store the required result int ans = 0; // If K is in the first // N / 2 elements, print K * 2 if (K <= N / 2) { ans = K * 2; } // Otherwise, K is greater than N/2 else { // If N is even if (N % 2 == 0) { ans = (K * 2) - N - 1; } // If N is odd else { ans = (K * 2) - N; } } // Print the required result System.out.println(ans); } // Driver code public static void main(String[] args) { int N = 10, K = 3; // functions call findKthElement(N, K); } } // This code is contributed by Kingash.
Python3
# Python 3 program for the above approach # Function to find the Kth element # in the required permutation def findKthElement(N, K): # Store the required result ans = 0 # If K is in the first # N / 2 elements, print K * 2 if (K <= N / 2): ans = K * 2 # Otherwise, K is greater than N/2 else: # If N is even if (N % 2 == 0): ans = (K * 2) - N - 1 # If N is odd else: ans = (K * 2) - N # Print the required result print(ans) # Driver Code if __name__ == '__main__': N = 10 K = 3 findKthElement(N, K) # This code is contributed by ipg2016107.
C#
// C# program for the above approach using System; class GFG{ // Function to find the Kth element // in the required permutation static void findKthElement(int N, int K) { // Store the required result int ans = 0; // If K is in the first // N / 2 elements, print K * 2 if (K <= N / 2) { ans = K * 2; } // Otherwise, K is greater than N/2 else { // If N is even if (N % 2 == 0) { ans = (K * 2) - N - 1; } // If N is odd else { ans = (K * 2) - N; } } // Print the required result Console.Write(ans); } // Driver code static void Main() { int N = 10, K = 3; // functions call findKthElement(N, K); } } // This code is contributed by sanjoy_62.
Javascript
<script> // javascript program for the above approach // Function to find the Kth element // in the required permutation function findKthElement( N, K) { // Store the required result let ans = 0; // If K is in the first // N / 2 elements, print K * 2 if (K <= N / 2) { ans = K * 2; } // Otherwise, K is greater than N/2 else { // If N is even if (N % 2 == 0) { ans = (K * 2) - N - 1; } // If N is odd else { ans = (K * 2) - N; } } // Print the required result document.write(ans); } // Driver Code let N = 10, K = 3; findKthElement(N, K); // This code is contributed by todaysgaurav </script>
6
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA