Encuentre una permutación de longitud N que contenga subarreglos con una suma menor que Bitwise XOR

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:
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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *