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 5
Explanation:
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 4
Naive 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.
Algorithm
Define a function called last_elements_left that takes a vector of integers as input.
Get the size of the input vector arr and loop through each index i from 0 to n-1.
Create a new vector called suff that contains all the elements from arr starting from index i.
While the size of suff is greater than 1, do the following:
a. Create a new vector called new_suff with size suff.size() - 1.
b. Loop through each index j in new_suff and do the following:
i. Compute suff[j] | suff[j + 1] and store the result in temp.
ii. Compute suff[j] ^ suff[j + 1] and subtract the result from temp.
iii. Store the result of step ii in new_suff[j].
c. Set suff to new_suff.
Print the first and only element in suff.
C++
#include <iostream>#include <vector>using namespace std;void last_elements_left(vector<int> arr) { int n = arr.size(); for (int i = 0; i < n; i++) { // Create a suffix array by selecting all elements starting from i vector<int> suff(arr.begin() + i, arr.end()); // Repeatedly perform the given operations until only one element is left while (suff.size() > 1) { vector<int> new_suff(suff.size() - 1); for (int j = 0; j < suff.size() - 1; j++) { new_suff[j] = (suff[j] | suff[j + 1]) - (suff[j] ^ suff[j + 1]); } suff = new_suff; } // Print the last element left after the operations cout << suff[0] << " "; }}int main() { vector<int> arr = {2, 3, 6, 5}; last_elements_left(arr); // Output: 0 0 4 5 return 0;} |
Java
import java.util.ArrayList;public class Main { public static void lastElementsLeft(ArrayList<Integer> arr) { int n = arr.size(); for (int i = 0; i < n; i++) { // Create a suffix array by selecting all elements starting from i ArrayList<Integer> suff = new ArrayList<>(arr.subList(i, n)); // Repeatedly perform the given operations until only one element is left while (suff.size() > 1) { ArrayList<Integer> newSuff = new ArrayList<>(suff.size() - 1); for (int j = 0; j < suff.size() - 1; j++) { newSuff.add((suff.get(j) | suff.get(j + 1)) - (suff.get(j) ^ suff.get(j + 1))); } suff = newSuff; } // Print the last element left after the operations System.out.print(suff.get(0) + " "); } } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<>(); arr.add(2); arr.add(3); arr.add(6); arr.add(5); lastElementsLeft(arr); // Output: 0 0 4 5 }} |
Python3
def last_elements_left(arr): n = len(arr) for i in range(n): # Create a suffix array by selecting all elements starting from i suff = arr[i:] # Repeatedly perform the given operations until only one element is left while len(suff) > 1: new_suff = [0] * (len(suff)-1) for j in range(len(suff)-1): new_suff[j] = (suff[j] | suff[j+1]) - (suff[j] ^ suff[j+1]) suff = new_suff # Print the last element left after the operations print(suff[0], end=" ")# Example usage:arr = [2, 3, 6, 5]last_elements_left(arr) # Output: 0 0 4 5 |
C#
using System;using System.Collections.Generic;class MainClass{ static void lastElementsLeft(List<int> arr) { int n = arr.Count; for (int i = 0; i < n; i++) { // Create a suffix array by selecting all elements starting from i List<int> suff = new List<int>(arr.GetRange(i, n - i)); // Repeatedly perform the given operations until only one element is left while (suff.Count > 1) { List<int> newSuff = new List<int>(suff.Count - 1); for (int j = 0; j < suff.Count - 1; j++) { newSuff.Add((suff[j] | suff[j + 1]) - (suff[j] ^ suff[j + 1])); } suff = newSuff; } // Print the last element left after the operations Console.Write(suff[0] + " "); } } static void Main() { List<int> arr = new List<int>(); arr.Add(2); arr.Add(3); arr.Add(6); arr.Add(5); lastElementsLeft(arr); // Output: 0 0 4 5 }} |
Javascript
//Javascript codefunction last_elements_left(arr) { let n = arr.length; for (let i = 0; i < n; i++) {// Create a suffix array by selecting all elements starting from ilet suff = arr.slice(i);// Repeatedly perform the given operations until only one element is leftwhile (suff.length > 1) { let new_suff = new Array(suff.length - 1); for (let j = 0; j < suff.length - 1; j++) { new_suff[j] = (suff[j] | suff[j + 1]) - (suff[j] ^ suff[j + 1]); } suff = new_suff;}// Print the last element left after the operationsconsole.log(suff[0] + " "); }}let arr = [2, 3, 6, 5];last_elements_left(arr); // Output: 0 0 4 5// This code is contributed by Pushpesh Raj |
Output
0 0 4 5
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
// 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 themvoid 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 Codeint main(){ // Input int arr[] = { 2, 3, 6, 5 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call performOperation(arr, N);} |
Java
// Java program for the above approachimport java.io.*;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. |
Python3
# 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 themdef 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 Codeif __name__ == '__main__': # Input arr = [2, 3, 6, 5] N = len(arr) # Function call performOperation(arr, N) # This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing 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 themstatic 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 Codepublic 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 |
Javascript
<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> |
Output
0 0 4 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
