Dada una array arr[] (indexación basada en 1) que consta de N enteros, la tarea es encontrar el último elemento restante después de la eliminación repetida del elemento de la array en índices cuadrados perfectos .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 5
Explicación:
Después de la eliminación del elemento de array en los índices cuadrados perfectos que se realizan:
- La eliminación de elementos de array en los índices 1 y 4 modifica la array a {2, 3, 5}.
- La eliminación de elementos de array en los índices 1 modifica la array a {3, 5}.
- Al eliminar los elementos de la array en los índices 1, la array se modifica a {5}.
Después de realizar las operaciones anteriores, el elemento de array que queda es 5. Por lo tanto, imprima 5.
Entrada: arr[] = {2, 3, 4, 4, 2, 4, -3, 1, 1}
Salida: -3
Enfoque ingenuo: el problema dado se puede resolver eliminando los elementos de la array en índices cuadrados perfectos y luego copiando todos los elementos en la nueva array. Siga realizando este paso hasta que solo quede un elemento en la array. Después de completar los pasos anteriores, imprima el último elemento que queda.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar encontrando los últimos elementos potenciales restantes de la array hasta que ese elemento no esté presente en índices cuadrados perfectos. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos ans como N que almacene los últimos índices restantes después de realizar las operaciones dadas.
- Iterar hasta que el valor de N sea mayor que 1 y realizar los siguientes pasos:
- Encuentre la cantidad de elementos que se pueden descartar, digamos D como sqrt(N) .
- Si el cuadrado de D es N , entonces N no puede ser el último elemento restante, ya que se elimina. Así que disminuya el valor de ans en 1 como los siguientes índices potenciales restantes.
- Disminuir el valor de N por D .
- Después de completar los pasos anteriores, imprima el elemento en el índice (D – 1) como el elemento restante posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find last remaining index
// after repeated removal of perfect
// square indices
int findRemainingIndex(int N)
{
// Initialize the ans variable as N
int ans = N;
// Iterate a while loop and discard
// the possible values
while (N > 1) {
// Total discarded values
int discard = int(sqrt(N));
// Check if this forms a
// perfect square
if (discard * discard == N) {
// Decrease answer by 1
ans--;
}
// Subtract the value from
// the current value of N
N -= discard;
}
// Return the value remained
return ans;
}
// Function to find last remaining element
// after repeated removal of array element
// at perfect square indices
void findRemainingElement(int arr[], int N)
{
// Find the remaining index
int remainingIndex = findRemainingIndex(N);
// Print the element at that
// index as the result
cout << arr[remainingIndex - 1];
}
// Driver Code
signed main()
{
int arr[] = { 2, 3, 4, 4, 2, 4, -3, 1, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
findRemainingElement(arr, N);
return 0;
}
Java
// Java implementation of the above approach
import java.util.*;
import java.lang.*;
import java.lang.Math;
class GFG {
// Function to find last remaining index
// after repeated removal of perfect
// square indices
static int findRemainingIndex(int N)
{
// Initialize the ans variable as N
int ans = N;
// Iterate a while loop and discard
// the possible values
while (N > 1) {
// Total discarded values
int discard = (int)(Math.sqrt(N));
// Check if this forms a
// perfect square
if (discard * discard == N) {
// Decrease answer by 1
ans--;
}
// Subtract the value from
// the current value of N
N -= discard;
}
// Return the value remained
return ans;
}
// Function to find last remaining element
// after repeated removal of array element
// at perfect square indices
static void findRemainingElement(int arr[], int N)
{
// Find the remaining index
int remainingIndex = findRemainingIndex(N);
// Print the element at that
// index as the result
System.out.print(arr[remainingIndex - 1]);
}
// Driver Code
public static void main(String[] args)
{
// Given input
int arr[] = { 2, 3, 4, 4, 2, 4, -3, 1, 1 };
int N = 9;
findRemainingElement(arr, N);
}
}
// This code is contributed by dwivediyash
Python3
# Python 3 program for the above approach from math import sqrt # Function to find last remaining index # after repeated removal of perfect # square indices def findRemainingIndex(N): # Initialize the ans variable as N ans = N # Iterate a while loop and discard # the possible values while (N > 1): # Total discarded values discard = int(sqrt(N)) # Check if this forms a # perfect square if (discard * discard == N): # Decrease answer by 1 ans -= 1 # Subtract the value from # the current value of N N -= discard # Return the value remained return ans # Function to find last remaining element # after repeated removal of array element # at perfect square indices def findRemainingElement(arr, N): # Find the remaining index remainingIndex = findRemainingIndex(N) # Print the element at that # index as the result print(arr[remainingIndex - 1]) # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 4, 2, 4, -3, 1, 1] N = len(arr) findRemainingElement(arr, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG {
// Function to find last remaining index
// after repeated removal of perfect
// square indices
static int findRemainingIndex(int N)
{
// Initialize the ans variable as N
int ans = N;
// Iterate a while loop and discard
// the possible values
while (N > 1) {
// Total discarded values
int discard = (int)(Math.Sqrt(N));
// Check if this forms a
// perfect square
if (discard * discard == N) {
// Decrease answer by 1
ans--;
}
// Subtract the value from
// the current value of N
N -= discard;
}
// Return the value remained
return ans;
}
// Function to find last remaining element
// after repeated removal of array element
// at perfect square indices
static void findRemainingElement(int[] arr, int N)
{
// Find the remaining index
int remainingIndex = findRemainingIndex(N);
// Print the element at that
// index as the result
Console.Write(arr[remainingIndex - 1]);
}
// Driver Code
public static void Main()
{
// Given input
int[] arr = { 2, 3, 4, 4, 2, 4, -3, 1, 1 };
int N = 9;
findRemainingElement(arr, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find last remaining index
// after repeated removal of perfect
// square indices
function findRemainingIndex(N) {
// Initialize the ans variable as N
let ans = N;
// Iterate a while loop and discard
// the possible values
while (N > 1) {
// Total discarded values
let discard = Math.floor(Math.sqrt(N));
// Check if this forms a
// perfect square
if (discard * discard == N) {
// Decrease answer by 1
ans--;
}
// Subtract the value from
// the current value of N
N -= discard;
}
// Return the value remained
return ans;
}
// Function to find last remaining element
// after repeated removal of array element
// at perfect square indices
function findRemainingElement(arr, N) {
// Find the remaining index
let remainingIndex = findRemainingIndex(N);
// Print the element at that
// index as the result
document.write(arr[remainingIndex - 1]);
}
// Driver Code
let arr = [2, 3, 4, 4, 2, 4, -3, 1, 1];
let N = arr.length;
findRemainingElement(arr, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
-3
Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA