Tuesday, 26 Oct 2021

# Construct array B as last element left of every suffix array obtained by performing given operations on every suffix of given array

Given an array arr[] of N integers, the task is to print the last element left of every suffix array obtained by performing the following operation on every suffix of the array, arr[]:Copy the elements of the suffix array into an array suff[].Update ith suffix element as suff[i] = (suff[i] OR suff[i+1]) – (suff[i] XOR suff[i+1]) reducing the size of suffix array by 1.Repeat the above step, until the size of the suffix array is not 1.Examples:Input: arr[] = {2, 3, 6, 5}Output: 0 0 4 5Explanation: Perform the operations as follows:Suffix array {2, 3, 6, 5}:In the first step, the array modifies to {2, 2, 4}.In the second step, the array modifies to {2, 0}In the third step, the array modifies to {0}.Therefore, the last element left is 0.Suffix array {3, 6, 5}:In the first step, the array modifies to {2, 4}.In the second step, the array modifies to {0}Therefore, the last element left is 0.Suffix array {6, 5}:In the first step, the array modifies to {4}Therefore, the last element left is 4.Suffix array {5}:It has only one element. Therefore, the last element left is 5.Input: arr[] = {1, 2, 3, 4}Output: 0 0 0 4Naive Approach: The simplest approach is to traverse every suffix array and perform the above-given operations by iterating over the suffix array and then print the value obtained.Time Complexity: O(N2)Auxiliary Space: O(N)Efficient Approach: The given problem can be solved based on the following observations: From the bitwise property:(X | Y) — (X ^ Y) = (X & Y)Therefore, from the above, the last value obtained is the bitwise AND of all the elements of the suffix array after performing the given operation on the suffix array.Follow the steps below to solve the problem:Iterate in the range [0, N-2] and in reverse order using the variable i and in each iteration update the arr[i] to arr[i] & arr[i+1].Iterate in the range [0, N-1] and using a variable i and perform the following steps:Print the value stored in arr[i] as the answer for the suffix array over the range [i, N-1].Below is the implementation of the above approach:C++14#include using namespace std;void performOperation(int arr[], int N){            for (int i = N – 2; i >= 0; i–) {        arr[i] = arr[i] & arr[i + 1];    }        for (int i = 0; i < N; i++)        cout