Último elemento de una array después de eliminar repetidamente el primer elemento y agregarlo al final de la array dos veces exactamente K veces

Dada una array arr[] que consta de N enteros y un entero positivo K , la tarea es encontrar el último elemento presente en la array obtenida al eliminar repetidamente el primer elemento de la array y agregarlo dos veces al final de la array K veces .

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}, K = 5
Salida: 5
Explicación:
Inicialmente, la array es {1, 2, 3, 4, 5}. Las siguientes operaciones se realizan K(= 5) número de veces:
Después de la ^primera operación, la array se modifica a {2, 3, 4, 5, 1, 1}.
Después de la ^segunda operación, la array se modifica a {3, 4, 5, 1, 1, 2, 2}.
Después de la tercera ^operación , la array se modifica a {4, 5, 1, 1, 2, 2, 3, 3}.
Después de la ^4ª operación, la array se modifica a {5, 1, 1, 2, 2, 3, 3, 4, 4}.
Después de la ^quinta operación, la array se modifica a {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}.
Después de completar las operaciones anteriores, el último elemento es 5. Por lo tanto, la respuesta es 5.

Entrada: arr[] = {1, 2, 3}, K = 7
Salida: 2

Enfoque: El problema dado se puede resolver observando el siguiente patrón:

Considere una array arr[] = {1, 2, 3, 4, 5}
Después de las primeras 5 operaciones, la array se modifica a {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}.
Después de las primeras 10 operaciones, la array se modifica a {1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5} .

Por lo tanto, el tamaño de la array después de N * 2 ^K operaciones es 2 * N * 2 ^K.

Siga los pasos a continuación para resolver el problema:

• Itere un ciclo desde el valor 0 usando la variable j y actualice el valor de K como (K – N * 2 ^j ) hasta que K sea mayor que N * 2 ^j .
• Después de completar los pasos anteriores, inicialice una variable, digamos r como 2 ^j , donde cada valor se repite R número de veces.
• Inicialice una variable, digamos M como 1 , que almacena el índice del carácter en la array arr[] que es igual al último carácter después de realizar K operaciones.
• Itere sobre el rango [1, N] usando la variable i y si el valor de K es mayor que R * i , entonces incremente M en 1 .
• Después de completar los pasos anteriores, imprima el valor de arr[M – 1] como el último elemento resultante de la array .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the last element
// after performing given operations
void findLastElement(int N, vector<int> A)
{
     
    // Length of the array
    int l = A.size();
 
    int j = 0;
 
    // Increment j until
    // condition is satisfied
    while (N > l * (pow(2, j)))
    {
        N = N - l * pow(2, j);
        j += 1;
    }
 
    int k = 1;
 
    // In each pair every value is
    // repeating r number of times
    int r = pow(2, j);
    for(int i = 1; i < l; i++)
    {
        if (N > r * i)
            k += 1;
    }
 
    // Print the result according
    // to the value of k
    for(int i = 0; i < l; i++)
    {
        if (i + 1 == k)
        {
            cout << (A[i]);
            return;
        }
    }
}
 
// Driver Code
int main()
{
     
    // Given K
    int K = 7;
     
    // Given arr[]
    vector<int> A = { 1, 2, 3 };
     
    // Function call
    findLastElement(K, A);
     
    return 0;
}
 
// This code is contributed by mohit kumar 29

// Java program for the above approach
import java.io.*;
class GFG
{
   
    // Function to find the last element
    // after performing given operations
    static void findLastElement(int N, int[] A)
    {
 
        // Length of the array
        int l = A.length;
 
        int j = 0;
 
        // Increment j until
        // condition is satisfied
        while (N > l * (int)(Math.pow(2, j))) {
            N = N - l * (int)Math.pow(2, j);
            j += 1;
        }
 
        int k = 1;
 
        // In each pair every value is
        // repeating r number of times
        int r = (int)Math.pow(2, j);
        for (int i = 1; i < l; i++) {
            if (N > r * i)
                k += 1;
        }
 
        // Print the result according
        // to the value of k
        for (int i = 0; i < l; i++) {
            if (i + 1 == k) {
                System.out.print(A[i]);
                return;
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given K
        int K = 7;
 
        // Given arr[]
        int[] A = { 1, 2, 3 };
 
        // Function call
        findLastElement(K, A);
    }
}
 
// This code is contributed by subham348.

# Python program for the above approach
 
# Function to find the last element
# after performing given operations
def findLastElement(N, A):
 
    # Length of the array
    l = len(A)
 
    j = 0
 
    # Increment j until
    # condition is satisfied
    while(N > l*(2**j)):
        N = N - l * 2**j
        j += 1
 
    k = 1
 
    # In each pair every value is
    # repeating r number of times
    r = 2**j
    for i in range(1, l):
        if N > r * i:
            k += 1
 
    # Print the result according
    # to the value of k
    for i in range(0, len(A)):
        if(i + 1 == k):
            print(A[i])
            return
 
 
# Driver Code
if __name__ == '__main__':
 
      # Given K
    K = 7
 
    # Given arr[]
    A = [1, 2, 3]
 
    # Function call
    findLastElement(K, A)

// C# program for the above approach
using System;
 
class GFG{
 
    // Function to find the last element
    // after performing given operations
    static void findLastElement(int N, int[] A)
    {
  
        // Length of the array
        int l = A.Length;
  
        int j = 0;
  
        // Increment j until
        // condition is satisfied
        while (N > l * (int)(Math.Pow(2, j))) {
            N = N - l * (int)Math.Pow(2, j);
            j += 1;
        }
  
        int k = 1;
  
        // In each pair every value is
        // repeating r number of times
        int r = (int)Math.Pow(2, j);
        for (int i = 1; i < l; i++) {
            if (N > r * i)
                k += 1;
        }
  
        // Print the result according
        // to the value of k
        for (int i = 0; i < l; i++) {
            if (i + 1 == k) {
                Console.WriteLine(A[i]);
                return;
            }
        }
    }
 
// Driver Code
public static void Main(String[] args)
{
    // Given K
        int K = 7;
  
        // Given arr[]
        int[] A = { 1, 2, 3 };
  
        // Function call
        findLastElement(K, A);
}
}
 
// This code is contributed by target_62.

<script>
 
// JavaScript program for the above approach
 
// Function to find the last element
// after performing given operations
function findLastElement(N, A)
{
     
    // Length of the array
    let l = A.length;
 
    let j = 0;
 
    // Increment j until
    // condition is satisfied
    while (N > l * (Math.pow(2, j)))
    {
        N = N - l * Math.pow(2, j);
        j += 1;
    }
 
    let k = 1;
 
    // In each pair every value is
    // repeating r number of times
    let r = Math.pow(2, j);
    for(let i = 1; i < l; i++)
    {
        if (N > r * i)
            k += 1;
    }
 
    // Print the result according
    // to the value of k
    for(let i = 0; i < l; i++)
    {
        if (i + 1 == k)
        {
            document.write(A[i]);
            return;
        }
    }
}
 
// Driver Code
     
    // Given K
    let K = 7;
     
    // Given arr[]
    let A = [ 1, 2, 3 ];
     
    // Function call
    findLastElement(K, A);
     
</script>

2

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)