Encuentre la posición del último elemento eliminado de la array

Dada una array de tamaño  y un número entero  . Realice las siguientes operaciones en la array dada: 

1. Si a[i] > M , entonces presione a[i] – M hasta el final de la array; de lo contrario, elimínelo de la array.
2. Realice la primera operación mientras la array no esté vacía.

La tarea es encontrar la posición original del último elemento que se eliminó. 

Ejemplos:  

Entrada: arr[] = {4, 3}, M = 2 
Salida: 2 
Elimina 4 de la array y la array se convierte en {3, 2} con las posiciones originales {2, 1} 
Elimina 3 de la array y la array se convierte en { 2, 1} con posiciones originales {1, 2} 
Elimina 2 de la array y la array se convierte en {1} con posiciones originales {2} 
Por lo tanto, el segundo elemento posicionado es el último que se elimina de la array.

Entrada: arr[] = {2, 5, 4}, M = 2 
Salida: 2 
 

La idea es observar el último elemento que se eliminará de la array. Se puede decir fácilmente que el último elemento que se eliminará será el elemento que se puede restar el número máximo de veces  entre todos los elementos de la array. Es decir, el elemento con valor máximo de ceil(a[i] / M) .

Entonces, la tarea ahora se reduce a encontrar el índice del elemento en la array con el valor máximo de ceil(a[i] / M) .

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

// C++ program to find the position of the
// last removed element from the array
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the original position
// of the element which will be
// removed last
int getPosition(int a[], int n, int m)
{
    // take ceil of every number
    for (int i = 0; i < n; i++) {
        a[i] = (a[i] / m + (a[i] % m != 0));
    }
 
    int ans = -1, max = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (max < a[i]) {
            max = a[i];
            ans = i;
        }
    }
 
    // Since position is index+1
    return ans + 1;
}
 
// Driver code
int main()
{
    int a[] = { 2, 5, 4 };
 
    int n = sizeof(a) / sizeof(a[0]);
 
    int m = 2;
 
    cout << getPosition(a, n, m);
 
    return 0;
}

// Java program to find the position of the
// last removed element from the array
import java.util.*;
 
class solution
{
 
// Function to find the original position
// of the element which will be
// removed last
 
static int getPosition(int a[], int n, int m)
{
    // take ceil of every number
    for (int i = 0; i < n; i++) {
        a[i] = (a[i] / m + (a[i] % m));
    }
 
    int ans = -1, max = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (max < a[i]) {
            max = a[i];
            ans = i;
        }
    }
 
    // Since position is index+1
    return ans + 1;
}
 
// Driver code
public static void main(String args[])
{
    int a[] = { 2, 5, 4 };
 
    int n = a.length;
 
    int m = 2;
 
System.out.println(getPosition(a, n, m));
 
}
 
}
//This code is contributed by
// Surendra_Gangwar

# Python3 program to find the position of
# the last removed element from the array
import math as mt
 
# Function to find the original
# position of the element which
# will be removed last
def getPosition(a, n, m):
 
    # take ceil of every number
    for i in range(n):
        a[i] = (a[i] // m +
               (a[i] % m != 0))
     
    ans, maxx = -1,-1
    for i in range(n - 1, -1, -1):
        if (maxx < a[i]):
            maxx = a[i]
            ans = i
             
    # Since position is index+1
    return ans + 1
 
# Driver code
a = [2, 5, 4]
 
n = len(a)
 
m = 2
 
print(getPosition(a, n, m))
 
# This is contributed by Mohit kumar 29

// C# program to find the position of the
// last removed element from the array
using System;
 
class GFG
{
     
// Function to find the original
// position of the element which
// will be removed last
static int getPosition(int []a,
                       int n, int m)
{
    // take ceil of every number
    for (int i = 0; i < n; i++)
    {
        a[i] = (a[i] / m + (a[i] % m));
    }
 
    int ans = -1, max = -1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (max < a[i])
        {
            max = a[i];
            ans = i;
        }
    }
 
    // Since position is index+1
    return ans + 1;
}
 
// Driver code
static public void Main ()
{
    int []a = { 2, 5, 4 };
    int n = a.Length;
    int m = 2;
    Console.WriteLine(getPosition(a, n, m));
}
}
 
// This code is contributed by ajit

<?php
// PHP program to find the position of the
// last removed element from the array
 
// Function to find the original
// position of the element which
// will be removed last
function getPosition($a, $n, $m)
{
    // take ceil of every number
    for ( $i = 0; $i < $n; $i++)
    {
        $a[$i] = ($a[$i] / $m +
                 ($a[$i] % $m != 0));
    }
 
    $ans = -1;
    $max = -1;
    for ($i = $n - 1; $i >= 0; $i--)
    {
        if ($max < $a[$i])
        {
            $max = $a[$i];
            $ans = $i;
        }
    }
 
    // Since position is index+1
    return $ans + 1;
}
 
// Driver code
$a = array( 2, 5, 4 );
$n = sizeof($a);
$m = 2;
 
echo getPosition($a, $n, $m);
 
// This code is contributed by jit_t
?>

<script>
 
// Javascript program to find the position
// of the last removed element from the array
 
// Function to find the original
// position of the element which
// will be removed last
function getPosition(a, n, m)
{
     
    // Take ceil of every number
    for(let i = 0; i < n; i++)
    {
        a[i] = (a[i] / m + (a[i] % m));
    }
 
    let ans = -1, max = -1;
    for(let i = n - 1; i >= 0; i--)
    {
        if (max < a[i])
        {
            max = a[i];
            ans = i;
        }
    }
 
    // Since position is index+1
    return ans + 1;
}
 
// Driver code
let a = [ 2, 5, 4 ];
let n = a.length;
let m = 2;
 
document.write(getPosition(a, n, m));
 
// This code is contributed by rameshtravel07
 
</script>

2

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)