Dada una array arr[] de N enteros positivos y un entero K , la tarea es encontrar el número mínimo de inserciones de cualquier entero positivo necesario para que la suma de todos los elementos adyacentes sea como máximo K . Si no es posible, imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}, K = 6
Salida: 2
Explicación:
Se requieren las siguientes inserciones:
Operación 1: Insertar 1 entre los índices 2 y 3. Por lo tanto, la array se modifica a {1 , 2, 3, 1, 4, 5}.
Operación 2: Inserte 1 entre el índice 4 y 5. Por lo tanto, la array se modifica a {1, 2, 3, 1, 4, 1, 5}. Por lo tanto, el número mínimo de inserciones necesarias es de 2.Entrada: arr[] = {4, 5, 6, 7, 7, 8}, K = 8
Salida: -1
Enfoque: La idea se basa en el hecho de que al insertar 1 entre los elementos cuya suma excede a K , la suma de los elementos consecutivos es menor que K si el elemento en sí no es igual o mayor que K. Siga los pasos a continuación para resolver el problema dado:
- Inicialice tres variables, digamos res = 0 , possible = 1 y last = 0 para almacenar el recuento de inserciones mínimas, para verificar si es posible hacer la suma de todos los pares consecutivos como máximo K o no, y para almacenar el anterior número al elemento actual respectivamente.
- Recorra la array arr[] y realice los siguientes pasos:
- Si el valor de arr[i] es al menos K , entonces no es posible hacer la suma de todos los pares consecutivos como máximo K .
- Si la suma de last y arr[i] es mayor que K , entonces incremente res en 1 y asigne last = arr[i] .
- Después de completar los pasos anteriores, si el valor de posible es 1 , imprima el valor de res como el número mínimo de inserciones requeridas. De lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count minimum number of
// insertions required to make sum of
// every pair of adjacent elements at most K
void minimumInsertions(int arr[],
int N, int K)
{
// Stores if it is possible to
// make sum of each pair of
// adjacent elements at most K
bool possible = 1;
// Stores the count of insertions
int res = 0;
// Stores the previous
// value to index i
int last = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater
// than or equal to K
if (arr[i] >= K) {
// Mark possible 0
possible = 0;
break;
}
// If last + arr[i]
// is greater than K
if (last + arr[i] > K)
// Increment res by 1
res++;
// Assign arr[i] to last
last = arr[i];
}
// If possible to make the sum of
// pairs of adjacent elements at most K
if (possible) {
cout << res;
}
// Otherwise print "-1"
else {
cout << "-1";
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 6;
int N = sizeof(arr) / sizeof(arr[0]);
minimumInsertions(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count minimum number of
// insertions required to make sum of
// every pair of adjacent elements at most K
static void minimumInsertions(int arr[],
int N, int K)
{
// Stores if it is possible to
// make sum of each pair of
// adjacent elements at most K
boolean possible = true;
// Stores the count of insertions
int res = 0;
// Stores the previous
// value to index i
int last = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater
// than or equal to K
if (arr[i] >= K) {
// Mark possible 0
possible = false;
break;
}
// If last + arr[i]
// is greater than K
if (last + arr[i] > K)
// Increment res by 1
res++;
// Assign arr[i] to last
last = arr[i];
}
// If possible to make the sum of
// pairs of adjacent elements at most K
if (possible) {
System.out.print(res);
}
// Otherwise print "-1"
else {
System.out.print("-1");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int K = 6;
int N = arr.length;
minimumInsertions(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach
# Function to count minimum number of
# insertions required to make sum of
# every pair of adjacent elements at most K
def minimumInsertions(arr, N, K):
# Stores if it is possible to
# make sum of each pair of
# adjacent elements at most K
possible = 1
# Stores the count of insertions
res = 0
# Stores the previous
# value to index i
last = 0
# Traverse the array
for i in range(N):
# If arr[i] is greater
# than or equal to K
if (arr[i] >= K):
# Mark possible 0
possible = 0
break
# If last + arr[i]
# is greater than K
if (last + arr[i] > K):
# Increment res by 1
res += 1
# Assign arr[i] to last
last = arr[i]
# If possible to make the sum of
# pairs of adjacent elements at most K
if (possible):
print(res)
# Otherwise print "-1"
else:
print("-1")
# Driver Code
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
K = 6
N = len(arr)
minimumInsertions(arr, N, K)
# This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
// Function to count minimum number of
// insertions required to make sum of
// every pair of adjacent elements at most K
static void minimumInsertions(int[] arr,
int N, int K)
{
// Stores if it is possible to
// make sum of each pair of
// adjacent elements at most K
bool possible = true;
// Stores the count of insertions
int res = 0;
// Stores the previous
// value to index i
int last = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// If arr[i] is greater
// than or equal to K
if (arr[i] >= K) {
// Mark possible 0
possible = false;
break;
}
// If last + arr[i]
// is greater than K
if (last + arr[i] > K)
// Increment res by 1
res++;
// Assign arr[i] to last
last = arr[i];
}
// If possible to make the sum of
// pairs of adjacent elements at most K
if (possible) {
Console.Write(res);
}
// Otherwise print "-1"
else {
Console.Write("-1");
}
}
// Driver code
static void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int K = 6;
int N = arr.Length;
minimumInsertions(arr, N, K);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to count minimum number of
// insertions required to make sum of
// every pair of adjacent elements at most K
function minimumInsertions(arr , N , K) {
// Stores if it is possible to
// make sum of each pair of
// adjacent elements at most K
var possible = true;
// Stores the count of insertions
var res = 0;
// Stores the previous
// value to index i
var last = 0;
// Traverse the array
for (i = 0; i < N; i++) {
// If arr[i] is greater
// than or equal to K
if (arr[i] >= K) {
// Mark possible 0
possible = false;
break;
}
// If last + arr[i]
// is greater than K
if (last + arr[i] > K)
// Increment res by 1
res++;
// Assign arr[i] to last
last = arr[i];
}
// If possible to make the sum of
// pairs of adjacent elements at most K
if (possible) {
document.write(res);
}
// Otherwise print "-1"
else {
document.write("-1");
}
}
// Driver Code
var arr = [ 1, 2, 3, 4, 5 ];
var K = 6;
var N = arr.length;
minimumInsertions(arr, N, K);
// This code contributed by umadevi9616
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA