Dada una array arr[] de tamaño N , la tarea es encontrar el número mínimo de pasos necesarios para reducir todos los elementos de la array a 0 excepto el primero y el último, donde en cada paso:
- Elija cualquier índice i (0<i<N-1) y disminuya el elemento en ese índice (arr[i]) en 2
- Luego incremente dos elementos cualquiera, arr[j], donde 0<=j<i y arr[k], donde i<k<n, en 1.
Si no es posible reducir la array dada como se desea, devuelva -1.
Entrada: arr[] = {2, 3, 3, 4, 7}
Salida: 6
Explicación: Considere los siguientes pasos como cómo se realizará la reducciónarray de pasos
0 {2, 3, 3, 4, 7} array original
1 {2, 4, 1, 4, 8} restar 2 de a[2] agregarlo a a[1] y a[4]
2 {3 , 2, 2, 4, 8} restar 2 de a[1] sumarlo a[0] y a[2]
3 {4, 0, 2, 4, 9} restar 2 de a[1] sumarlo a a[0] y a[4]
4 {5, 0, 0, 4, 10} restar 2 de a[2] sumarlo a a[0] y a[4]
5 {6, 0, 0, 2, 11} restar 2 de a[3] sumarlo a a[0] y a[4]
6 {7, 0, 0, 0, 12} restar 2 de a[3] sumarlo a a[0] y a[ 4]Entrada : arr[] = {3,2,1,3,5,4}
Salida : 7
Acercarse:
Intuición: el problema anterior se puede resolver con la ayuda de las siguientes observaciones:
- Caso 1: A[i] es par
- Como siempre restamos 2 de a[i], esto significa que a[i] debe ser un número par , de lo contrario, después de restar 2 cierto número de veces, quedará 1 sobre el cual no se podrá realizar ninguna operación más.
- Caso 2: A[i] es impar
- Entonces, para hacer que cada elemento sea 0, necesitamos tener números pares, y si no tenemos números pares, entonces tenemos que hacerlo par .
- Cuando restamos 2 de a[i], seleccionamos i tal que arr[i] es par y arr[j] y/o arr[k] son impares .
- Así que sumando 1 a ellos hará entonces un número par.
- Caso 3: Si no hay elemento impar
- Si no tenemos ningún número impar, podemos elegir el primer y el último elemento y sumar directamente 1 a a[0] y a[n-1] ya que no tenemos que reducir estos elementos.
Ilustración 1:
Supongamos que tenemos {3,2,1,3,5,4},
Paso 1: hay un elemento impar en la array. Así que elija el primer elemento impar en el rango de índice (0, N-1), es decir, a[2] = 1.
Tomamos 2 de a[1], agregamos 1 a a[0] y 1 a a[2].
Entonces la array se convierte en {4, 0, 2, 3, 5, 4}, y nuestro 1 se convierte en 2, que ahora es un número par.Paso 2: Ahora considere el siguiente número impar en el rango (0, N-1), es decir, a[3] = 3.
Tomamos 2 de a[2], agregamos 1 a a[0] y 1 a a[2].Entonces la array se convierte en {5, 0, 0, 4, 5, 4}, y nuestro 3 se convierte en 4, que ahora es un número par.
Paso 3: Ahora considere el siguiente número impar en el rango (0, N-1), es decir, a[4] = 5.
Tomamos 2 de a[3], agregamos 1 a a[0] y 1 a a[4].Entonces la array se convierte en {6, 0, 0, 2, 6, 4}, y nuestro 5 se convierte en 6, que ahora es un número par.
Paso 4 – 7: tomamos 2 de cada número par, es decir, 2 y 6, y lo cambiamos a a[0] y a[n-1]
Como en cada paso podemos reducirlo en 2, por lo que necesitaremos 1 paso para el elemento 2 y 3 pasos para el elemento 6.Por lo tanto, las operaciones totales se convierten en 7 y, finalmente, la array se convierte en {10, 0, 0, 0, 0, 8}.
Ilustración 2:
Ahora, si solo tenemos 3 elementos y el valor medio es un número impar,
entonces la respuesta no es posible porque la única selección posible es j=0,i=1 y k=2.Entonces, después de restar 2, un cierto número de veces a[i] se convertirá en 1.
Entonces, en este caso, no es posible una respuesta válida, y la respuesta será -1.
A continuación se muestra la implementación:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to shift the array
int stepsToRearrange(vector<int>& A, int n)
{
// if A has 3 elements and
// 2nd element is odd then
// answer is not possible
if (n == 3 && (A[1] % 2 == 1))
return -1;
int steps = 0, countOne = 0;
// Select even numbers and subtract 2
// Now for the odd number
// we add one and make them even.
// so total steps = (a[i]+1)/2
for (int i = 1; i < n - 1; i++) {
steps += (A[i] + 1) / 2;
countOne += (A[i] == 1);
}
// If all numbers in index 1 to n-2 = 1
// then answer is not possible
if (countOne == n - 2)
return -1;
// return steps
return steps;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 2, 1, 3, 5, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << stepsToRearrange(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to shift the array
public static int stepsToRearrange(int A[], int n)
{
// if A has 3 elements and
// 2nd element is odd then
// answer is not possible
if (n == 3 && (A[1] % 2 == 1))
return -1;
int steps = 0, countOne = 0;
// Select even numbers and subtract 2
// Now for the odd number
// we add one and make them even.
// so total steps = (a[i]+1)/2
for (int i = 1; i < n - 1; i++) {
steps += (A[i] + 1) / 2;
if (A[i] == 1) {
countOne += 1;
}
}
// If all numbers in index 1 to n-2 = 1
// then answer is not possible
if (countOne == n - 2)
return -1;
// return steps
return steps;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1, 3, 5, 4 };
int N = arr.length;
System.out.print(stepsToRearrange(arr, N));
}
}
// This code is contributed by Taranpreet
Python3
# python3 program for the above approach # Function to shift the array def stepsToRearrange(A, n): # if A has 3 elements and # 2nd element is odd then # answer is not possible if (n == 3 and (A[1] % 2 == 1)): return -1 steps, countOne = 0, 0 # Select even numbers and subtract 2 # Now for the odd number # we add one and make them even. # so total steps = (a[i]+1)/2 for i in range(1, n-1): steps += (A[i] + 1) // 2 countOne += (A[i] == 1) # If all numbers in index 1 to n-2 = 1 # then answer is not possible if (countOne == n - 2): return -1 # return steps return steps # Driver Code if __name__ == "__main__": arr = [3, 2, 1, 3, 5, 4] N = len(arr) print(stepsToRearrange(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG {
// Function to shift the array
static int stepsToRearrange(int[] A, int n)
{
// if A has 3 elements and
// 2nd element is odd then
// answer is not possible
if (n == 3 && (A[1] % 2 == 1))
return -1;
int steps = 0, countOne = 0;
// Select even numbers and subtract 2
// Now for the odd number
// we add one and make them even.
// so total steps = (a[i]+1)/2
for (int i = 1; i < n - 1; i++) {
steps += (A[i] + 1) / 2;
if (A[i] == 1) {
countOne += 1;
}
}
// If all numbers in index 1 to n-2 = 1
// then answer is not possible
if (countOne == n - 2)
return -1;
// return steps
return steps;
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 2, 1, 3, 5, 4 };
int N = arr.Length;
Console.Write(stepsToRearrange(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to shift the array
function stepsToRearrange(A, n)
{
// if A has 3 elements and
// 2nd element is odd then
// answer is not possible
if (n == 3 && (A[1] % 2 == 1))
return -1;
let steps = 0, countOne = 0;
// Select even numbers and subtract 2
// Now for the odd number
// we add one and make them even.
// so total steps = (a[i]+1)/2
for (let i = 1; i < n - 1; i++) {
steps += Math.floor((A[i] + 1) / 2);
countOne += (A[i] == 1);
}
// If all numbers in index 1 to n-2 = 1
// then answer is not possible
if (countOne == n - 2)
return -1;
// return steps
return steps;
}
// Driver Code
let arr = [ 3, 2, 1, 3, 5, 4 ];
let N = arr.length;
document.write(stepsToRearrange(arr, N));
// This code is contributed by Samim Hossain Mondal.
</script>
7
Complejidad temporal: O(N)
Espacio auxiliar: O(1)