Dado un entero positivo N , la tarea es encontrar una permutación de longitud N que tenga OR bit a bit de cualquiera de sus subarreglo mayor o igual a la longitud del subarreglo .
Ejemplos:
Entrada: N = 5
Salida: 1 3 5 2 4
Explicación:
Considere el subarreglo {1, 3, 5} de la permutación {1, 3, 5, 2, $}.
Longitud del subarreglo = 3
OR bit a bit del subarreglo = 1 | 3 | 5 = 7 (que es mayor que 3)
De manera similar, cada subarreglo de cualquier longitud menor que igual a N satisfará la condición.Entrada: 4
Salida: 4 3 1 2
Enfoque: En realidad, cualquier permutación de longitud N satisface las condiciones requeridas en base a los siguientes hechos:
- El OR bit a bit de cualquier conjunto de números es mayor o igual que el número máximo presente en ese conjunto.
- Dado que cualquier subarreglo contendrá al menos un elemento mayor o igual a su longitud, cualquier permutación satisface la condición dada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of // the above approach #include <iostream> using namespace std; // Function to print the // required permutation void findPermutation(int N) { for(int i = 1; i <= N; i++) cout << i << " "; cout << endl; } // Driver code int main() { int N = 5; findPermutation(N); return 0; }
Java
// Java implementation of // the above approach import java.util.*; class GFG{ // Function to print the // required permutation static void findPermutation(int N) { for(int i = 1; i <= N; i++) System.out.print(i + " "); } // Driver Code public static void main(String[] args) { int N = 5; findPermutation(N); } } // This code is contributed by susmitakundugoaldanga
Python3
# Python3 implementation of # the above approach # Function to print the # required permutation def findPermutation(N): for i in range(1, N + 1, 1): print(i, end= " ") print("\n", end = "") # Driver code if __name__ == '__main__': N = 5 findPermutation(N) # This code is contributed by ipg2016107.
C#
// C# implementation of // the above approach using System; class GFG{ // Function to print the // required permutation static void findPermutation(int N) { for(int i = 1; i <= N; i++) Console.Write(i + " "); } // Driver code public static void Main() { int N = 5; findPermutation(N); } } // This code is contributed by SURENDRA_GANGWAR
Javascript
<script> // javascript implementation of // the above approach // Function to print the // required permutation function findPermutation(N) { for(var i = 1; i <= N; i++) document.write( i + " "); document.write("<br>"); } var N = 5; findPermutation(N); //This code in contributed by SoumikMondal </script>
1 2 3 4 5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pawanharwani11 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA