Construya la array B como el último elemento que queda de cada array de sufijos obtenida al realizar las operaciones dadas en cada sufijo de la array dada

Dada una array arr[] de N enteros, la tarea es imprimir el último elemento que queda de cada array de sufijos obtenida realizando la siguiente operación en cada sufijo de la array, arr[] :

1. Copie los elementos de la array de sufijos en una array suff[] .
2. Actualice el i ^-ésimo elemento de sufijo como sufijo[i] = (suf[i] O sufijo[i+1]) – (suf[i] XOR sufijo[i+1]) reduciendo el tamaño de la array de sufijos en 1 .
3. Repita el paso anterior hasta que el tamaño de la array de sufijos no sea 1 .

Ejemplos:

Entrada: arr[] = {2, 3, 6, 5}
Salida: 0 0 4 5
Explicación: 
Realice las operaciones de la siguiente manera:

1. Array de sufijos {2, 3, 6, 5}:
   1. En el primer paso, la array se modifica a {2, 2, 4}.
   2. En el segundo paso, la array se modifica a {2, 0}
   3. En el tercer paso, la array se modifica a {0}.
   4. Por lo tanto, el último elemento que queda es 0.
2. Array de sufijos {3, 6, 5}:
   1. En el primer paso, la array se modifica a {2, 4}.
   2. En el segundo paso, la array se modifica a {0}
   3. Por lo tanto, el último elemento que queda es 0.
3. Array de sufijos {6, 5}:
   1. En el primer paso, la array se modifica a {4}
   2. Por lo tanto, el último elemento que queda es 4.
4. Array de sufijos {5}:
   1. Tiene un solo elemento. Por lo tanto, el último elemento que queda es 5.

Entrada: arr[] = {1, 2, 3, 4}
Salida: 0 0 0 4

Enfoque ingenuo: el enfoque más simple es recorrer cada array de sufijos y realizar las operaciones anteriores iterando sobre la array de sufijos y luego imprimir el valor obtenido.

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el problema dado se puede resolver con base en las siguientes observaciones: 

1. De la propiedad bit a bit :
   • (X | Y) — (X ^ Y) = (X e Y)
2. Por lo tanto, de lo anterior, el último valor obtenido es el AND bit a bit de todos los elementos de la array de sufijos después de realizar la operación dada en la array de sufijos.

Siga los pasos a continuación para resolver el problema:

• Iterar en el rango [0, N-2] y en orden inverso usando la variable i y en cada iteración actualizar arr[i] a arr[i] & arr[i+1] .
• Iterar en el rango [0, N-1] y usando una variable i y realizar los siguientes pasos:
  • Imprime el valor almacenado en arr[i] como la respuesta para la array de sufijos sobre el rango [i, N-1].

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the last element
// left of every suffix of the array
// after performing the given operati-
// ons on them
 
void performOperation(int arr[], int N)
{
    // Iterate until i is greater than
    // or equal to 0
    for (int i = N - 2; i >= 0; i--) {
        arr[i] = arr[i] & arr[i + 1];
    }
 
    // Print the array arr[]
    for (int i = 0; i < N; i++)
        cout << arr[i] << " ";
    cout << endl;
}
// Driver Code
int main()
{
    // Input
    int arr[] = { 2, 3, 6, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    performOperation(arr, N);
}

// Java program for the above approach
class GFG {
 
    // Function to find the last element
    // left of every suffix of the array
    // after performing the given operati-
    // ons on them
    public static void performOperation(int arr[], int N)
    {
       
        // Iterate until i is greater than
        // or equal to 0
        for (int i = N - 2; i >= 0; i--) {
            arr[i] = arr[i] & arr[i + 1];
        }
 
        // Print the array arr[]
        for (int i = 0; i < N; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver Code
    public static void main(String args[])
    {
       
        // Input
        int arr[] = { 2, 3, 6, 5 };
        int N = arr.length;
 
        // Function call
        performOperation(arr, N);
    }
}
 
// This code is contributed by saurabh_jaiswal.

# Python 3 program for the above approach
 
# Function to find the last element
# left of every suffix of the array
# after performing the given operati-
# ons on them
def performOperation(arr, N):
   
    # Iterate until i is greater than
    # or equal to 0
    i = N - 2
    while(i >= 0):
        arr[i] = arr[i] & arr[i + 1]
        i -= 1
 
    # Print the array arr[]
    for i in range(N):
        print(arr[i], end = " ")
     
# Driver Code
if __name__ == '__main__':
    # Input
    arr = [2, 3, 6, 5]
    N = len(arr)
 
    # Function call
    performOperation(arr, N)
     
    # This code is contributed by ipg2016107

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the last element
// left of every suffix of the array
// after performing the given operati-
// ons on them
static void performOperation(int []arr, int N)
{
     
    // Iterate until i is greater than
    // or equal to 0
    for(int i = N - 2; i >= 0; i--)
    {
        arr[i] = arr[i] & arr[i + 1];
    }
 
    // Print the array arr[]
    for(int i = 0; i < N; i++)
        Console.Write(arr[i] + " ");
         
    Console.WriteLine();
}
 
// Driver Code
public static void Main()
{
     
    // Input
    int []arr = { 2, 3, 6, 5 };
    int N = arr.Length;
 
    // Function call
    performOperation(arr, N);
}
}
 
// This code is contributed by ipg2016107

<script>
 
        // JavaScript program for the above approach
 
 
        // Function to find the last element
        // left of every suffix of the array
        // after performing the given operati-
        // ons on them
 
        function performOperation(arr, N) {
            // Iterate until i is greater than
            // or equal to 0
            for (let i = N - 2; i >= 0; i--) {
                arr[i] = arr[i] & arr[i + 1];
            }
 
            // Print the array arr[]
            for (let i = 0; i < N; i++)
                document.write(arr[i] + " ");
 
            document.write('<br>')
        }
        // Driver Code
 
        // Input
        let arr = [2, 3, 6, 5];
        let N = arr.length;
 
        // Function call
        performOperation(arr, N);
 
    // This code is contributed by Potta Lokesh
    </script>

0 0 4 5 

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)