- Arrays, Greedy, Mathematical, maths-perfect-square

Last element remaining after repeated removal of Array elements at perfect square indices

Given an array arr[](1-based indexing) consisting of N integers, the task is to find the last element remaining element after repeated removal of array element at perfect square indices.Examples:Input: arr[] = {1, 2, 3, 4, 5}Output: 5Explanation:Following the removal of array element at perfect square indices that are performed:Removing array elements at indices 1 and 4 modifies the array to {2, 3, 5}.Removing array elements at indices 1 modifies the array to {3, 5}.Removing array elements at indices 1 modifies the array to {5}.After performing the above operations, the array element remains is 5. Therefore, print 5. Input: arr[] = {2, 3, 4, 4, 2, 4, -3, 1, 1}Output: -3Naive Approach: The given problem can be solved by removing the array elements at perfect square indices and then copy all the elements to the new array. Keep performing this step until only one element remains in the array. After completing the above steps, print the last element that remains.Time Complexity: O(N2)Auxiliary Space: O(N)Efficient Approach: The above approach can also be optimized by finding the potential last remaining array elements until that element is not present at perfect square indices. Follow the steps below to solve the given problem:Initialize a variable, say ans as N that stores the last remaining indices after performing the given operations.Iterate until the value of N is greater than 1 and perform the following steps:Find the count of elements that can be discarded, say D as sqrt(N).If the square of D is N then N can’t be the last remaining element as it is removed. So decrement the value of ans by 1 as the next potential remaining indices.Decrement the value of N by D.After completing the above steps, print the element at index (D – 1) as the remaining possible element.Below is the implementation of the above approach: C++#include using namespace std;int findRemainingIndex(int N){        int ans = N;            while (N > 1) {                int discard = int(sqrt(N));                        if (discard * discard == N) {                        ans–;        }                        N -= discard;    }        return ans;}void findRemainingElement(int arr[], int N){        int remainingIndex = findRemainingIndex(N);            cout 1) {                  int discard = (int)(Math.sqrt(N));                          if (discard * discard == N) {                          ans–;        }                          N -= discard;    }          return ans;}  static void findRemainingElement(int arr[], int N){          int remainingIndex = findRemainingIndex(N);              System.out.print(arr[remainingIndex – 1]);}          public static void main(String[] args)    {                 int arr[] = { 2, 3, 4, 4, 2, 4, -3, 1, 1 };        int N = 9;        findRemainingElement(arr, N);         }}Python3from math import sqrtdef findRemainingIndex(N):        ans = N            while (N > 1):                discard = int(sqrt(N))                        if (discard * discard == N):                        ans -= 1                        N -= discard        return ansdef findRemainingElement(arr, N):           remainingIndex = findRemainingIndex(N)            print(arr[remainingIndex – 1])if __name__ == ‘__main__’:    arr = [2, 3, 4, 4, 2, 4, -3, 1, 1]    N = len(arr)    findRemainingElement(arr, N)         Javascript                                                function findRemainingIndex(N) {                        let ans = N;                                    while (N > 1) {                                let discard = Math.floor(Math.sqrt(N));                                                if (discard * discard == N) {                                        ans–;                }                                                N -= discard;            }                        return ans;        }                                function findRemainingElement(arr, N) {                        let remainingIndex = findRemainingIndex(N);                                    document.write(arr[remainingIndex – 1]);        }                let arr = [2, 3, 4, 4, 2, 4, -3, 1, 1];        let N = arr.length;        findRemainingElement(arr, N);      Output: -3Time Complexity: O(sqrt(N))Auxiliary Space: O(1)Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.