Dada una array circular de tamaño n que contiene números enteros del 1 al n. Encuentre el último elemento que permanecería en la lista después de borrar cada segundo elemento a partir del primer elemento.
Ejemplo:
Input: 5 Output: 3 Explanation Element in circular array are: 1 2 3 4 5 Starting from first element i.e, '1' delete every second element like this, 1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0 For demonstration purpose erased element would be treated as '0'. Thus at the end of list, the last element remains is 3. Input: 10 Output: 5
El enfoque Naive es eliminar cada segundo elemento de la array hasta que el tamaño de la array sea igual a ‘1’. La complejidad temporal de este enfoque es O(n 2 ) que no sería factible para un valor grande de ‘n’.
El enfoque Eficiente es usar la recursividad. Consideremos que n es par. En un recorrido, se eliminarán los números 2, 4, 6… N y comenzaremos nuevamente desde 1. Por lo tanto, se eliminarán exactamente n/2 números y comenzaremos como si fuera 1 en una array de N/2 que contiene solo dígitos impares 1, 3, 5, … n/2.
Por lo tanto, por esta intuición, su fórmula recursiva se puede escribir como,
If n is even: solve(n) = 2 * solve(n/2) - 1 else solve(n) = 2 * solve((n-1) / 2) + 1 Base condition would occur when n = 1, then answer would be 1.
Implementación:
C++
// C++ program return last number
// after removing every second
// element from circular array
#include<iostream>
using namespace std;
// Utility function to return last
// number after removing element
int removeAlternate(int n)
{
if (n == 1)
return 1;
if (n % 2 == 0)
return 2
* removeAlternate(n / 2)
- 1;
else
return 2
* removeAlternate(((n - 1) / 2))
+ 1;
}
// Driver code
int main()
{
int n = 5;
cout << removeAlternate(n) << "\n";
n = 10;
cout << removeAlternate(n) << "\n";
return 0;
}
Java
// Java program return
// last number after
// removing every second
// element from circular
// array
import java.util.*;
class Circular {
// Utility function to
// return last number
// number after removing
// element
public static int removeAlternate(int n)
{
if (n == 1)
return 1;
if (n % 2 == 0)
return 2
* removeAlternate(n / 2)
- 1;
else
return 2 *
removeAlternate(((n - 1) / 2))
+ 1;
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
System.out.print(removeAlternate(n));
n = 10;
System.out.print("\n" + removeAlternate(n));
}
}
// This code is contributed by rishabh_jain
Python3
# Python program return last number # after removing every second # element from circular array # Utility function to return last # number after removing element def removeAlternate(n): if (n == 1): return 1 if (n % 2 == 0): return 2 * removeAlternate(n / 2) - 1 else: return 2 * removeAlternate(((n - 1) / 2)) + 1 # Driver code n = 5 print(removeAlternate(n)) n = 10 print(removeAlternate(n)) # This code is contributed by Smitha Dinesh Semwal
C#
// C# program return last number after
// removing every second element from
// circular array
using System;
class Circular {
// Utility function to return last number
// number after removing element
public static int removeAlternate(int n)
{
if (n == 1)
return 1;
if (n % 2 == 0)
return 2
* removeAlternate(n / 2)
- 1;
else
return 2
* removeAlternate(((n - 1) / 2))
+ 1;
}
// Driver Code
public static void Main()
{
int n = 5;
Console.WriteLine(removeAlternate(n));
n = 10;
Console.WriteLine(removeAlternate(n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program return last number
// after removing every second
// element from circular array
// Utility function to return last
// number after removing element
function removeAlternate($n)
{
if ($n == 1)
return 1;
if ($n % 2 == 0)
return 2 * removeAlternate($n / 2) - 1;
else
return 2 * removeAlternate((($n - 1) /
2)) + 1;
}
// Driver code
$n = 5;
echo removeAlternate($n) , "\n";
$n = 10;
echo removeAlternate($n) , "\n";
// This code is contributed by ajit
?>
Javascript
<script>
//Javascript program return last number
// after removing every second
// element from circular array
// Utility function to return last
// number after removing element
function removeAlternate(n)
{
if (n == 1)
return 1;
if (n % 2 == 0)
return 2
* removeAlternate(n / 2)
- 1;
else
return 2
* removeAlternate(((n - 1) / 2))
+ 1;
}
// Driver code
let n = 5;
document.write(removeAlternate(n) + "<br>");
n = 10;
document.write(removeAlternate(n) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
3 5
Complejidad temporal: O(log(n))
Espacio auxiliar: O(1)
La mayoría Otro enfoque:
otro enfoque consiste en observar el patrón en el que se repiten los números. Observé que la salida eran todos los números impares incrementados en 2 cada vez que el valor de n aumentaba en uno y el valor se restablecía a ‘1’ en las potencias de 2.
Por ejemplo, las salidas fueron 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 respectivamente para el valor de n que va de 1 a 16.
Por lo tanto, este enfoque utiliza el valor más cercano de la potencia de 2 menor o igual que la entrada dada.
Implementación:
C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
// find the value nearest
// to power of 2
int nearestPowerof2(int n)
{
int p = (int)log2(n);
return p;
}
// eliminate n
int circularElimination(int n)
{
// power of 2
int power=nearestPowerof2(n);
int result=1+2*(n-pow(2,power));
return result;
}
// Driver Code
int main() {
int n=5;
// Function call
int result=circularElimination(n);
cout<<result<<"\n";
n=10;
result=circularElimination(n);
cout<<result<<"\n";
return 0;
}
Java
import java.io.*;
class GFG
{
// find the power of 2
static int highestPowerof2(int n)
{
int p = (int)(Math.log(n) / Math.log(2));
return p;
}
// eliminate the element n
static int circularElimination(int n)
{
// power of 2
int power = highestPowerof2(n);
int res = 1 + 2 * (int)(n - Math.pow(2, power));
return res;
}
// Driver Code
public static void main(String[] args)
{
int n = 5;
// Function call
System.out.println(circularElimination(n));
n = 10;
System.out.println(circularElimination(n));
}
}
Python3
# Find the value nearest # to power of 2 import math def nearestPowerof2(n): p = int(math.log2(n)) return p # Eliminate n def circularElimination(n): # power of 2 power = nearestPowerof2(n); result = (1 + 2 * (n - pow(2,power))) return result n = 5 # Driver code # Function call result = circularElimination(n) print(result) n = 10 result = circularElimination(n) print(result) # This code is contributed by divyeshrabadiya07
C#
using System;
class GFG{
// Find the power of 2
static int highestPowerof2(int n)
{
int p = (int)(Math.Log(n) /
Math.Log(2));
return p;
}
// Eliminate the element n
static int circularElimination(int n)
{
// Power of 2
int power = highestPowerof2(n);
int res = 1 + 2 * (int)(
n - Math.Pow(2, power));
return res;
}
// Driver Code
public static void Main(string[] args)
{
int n = 5;
// Function call
Console.WriteLine(circularElimination(n));
n = 10;
Console.WriteLine(circularElimination(n));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Find the power of 2
function highestPowerof2(n)
{
let p = parseInt(Math.log(n) / Math.log(2), 10);
return p;
}
// Eliminate the element n
function circularElimination(n)
{
// Power of 2
let power = highestPowerof2(n);
let res = 1 + 2 * (n - Math.pow(2, power));
return res;
}
let n = 5;
// Function call
document.write(circularElimination(n) + "</br>");
n = 10;
document.write(circularElimination(n));
</script>
3 5
Complejidad de tiempo: O(1)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por Shubham Bansal 13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA