Paridad del valor final después de la eliminación circular repetida de Kth Integer

Dado un número entero N , que denota el tamaño de un círculo donde los primeros N números enteros se colocan en el sentido de las agujas del reloj, de modo que j y (j+1) son adyacentes, y 1 y N también son adyacentes. Dado un entero K (K < N), la tarea es encontrar si el último valor restante es par o impar cuando en cada turno se elimina el K ^-ésimo elemento desde el principio (es decir, 1) y se realiza hasta que solo un elemento restos,

Ejemplos:

Entrada: N = 5, K = 1
Salida: Impar
Explicación: Aquí K = 1 significa que el primer elemento de posición se elimina de la array circular de 5 enteros, es decir, [ 1 , 2, 3, 4, 5]→[2, 3, 4, 5] y repita este paso hasta que solo quede un número entero, es decir, [ 2 , 3, 4, 5]→[ 3 , 4, 5]→[ 4 , 5]→[5]. Por lo tanto, el último entero es impar.

Entrada: N = 3, K = 3
Salida: Par

Planteamiento: El problema se puede resolver con base en la siguiente observación:

Observaciones:

• Si K = 1: Todos los números del 1 al N-1 se eliminan y solo queda N
• Si K = 2: Todos los números del 2 al N se eliminan y solo queda 1.
• Si K > 2: Se borran todos los números de K a N. Los números restantes son del 1 al K-1. Entonces, en cada turno, cuando se eliminan elementos, sigue un patrón como 1, 3, 5, . . . porque el tamaño de la lista disminuye en 1 después de cada iteración y los números totales hasta el siguiente número impar también disminuyen en 1. Entonces, todos los elementos impares se eliminan primero y luego los valores pares. Entonces, el último valor restante siempre es un número par.

Siga los pasos mencionados a continuación para implementar la observación:

• Compruebe el valor de K y N.
• Con base en sus valores, decida cuál de los casos anteriores es aplicable.
• Devuelve la paridad del elemento así obtenido.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the parity of the last element
int parity(int N, int K)
{
    if ((K == 1 && (N % 2 != 0)) || K == 2)
        return 1;
    return 0;
}
 
// Driver code
int main()
{
    int N = 5, K = 1;
 
    // Function call
    if (parity(N, K))
        cout << "Odd";
    else
        cout << "Even";
    return 0;
}

// Java code to implement the approach
 
import java.util.*;
 
class GFG {
 
    // Function to find the parity
    // of the last element
    public static int parity(int N, int K)
    {
        if (K == 2 || (N % 2 != 0 && K == 1))
            return 1;
        return 0;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 5, K = 1;
 
        // Function call
        if (parity(N, K) == 1)
            System.out.println("Odd");
        else
            System.out.println("Even");
    }
}

# Python code to implement the approach
 
# Function to find the parity of the last element
def parity(N, K):
    if (K == 1 and (N % 2 != 0)) or K == 2:
        return 1
    return 0
 
 
# Driver code
if __name__ == '__main__':
    N = 5
    K = 1
 
    # Function call
    if parity(N, K) == 1:
        print("Odd")
    else:
        print("Even")

// C# code to implement the approach
using System;
 
class GFG {
 
    // Function to find the parity
    // of the last element
    public static int parity(int N, int K)
    {
        if (K == 2 || (N % 2 != 0 && K == 1))
            return 1;
        return 0;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int N = 5, K = 1;
 
        // Function call
        if (parity(N, K) == 1)
            Console.WriteLine("Odd");
        else
            Console.WriteLine("Even");
    }
}
 
// This code is contributed by AnkThon

<script>
    // JavaScript code to implement the approach
 
    // Function to find the parity of the last element
    const parity = (N, K) => {
        if ((K == 1 && (N % 2 != 0)) || K == 2)
            return 1;
        return 0;
    }
 
    // Driver code
    let N = 5, K = 1;
 
    // Function call
    if (parity(N, K))
        document.write("Odd");
    else
        document.write("Even");
 
    // This code is contributed by rakeshsahni
 
</script>

Odd

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)