Dado un entero k y un arreglo op[] , en una sola operación se sumará op[0] a k y luego en la segunda operación k = k + op[1] y así sucesivamente de manera circular hasta k > 0 . La tarea es imprimir el número de operación en el que k se reducirá a ≤ 0 . Si es imposible reducir k con las operaciones dadas, imprima -1 .
Ejemplos:
Entrada: op[] = {-60, 10, -100}, k = 100
Salida: 3
Operación 1: 100 – 60 = 40
Operación 2: 40 + 10 = 50
Operación 3: 50 – 100 = -50
Entrada: op [] = {1, 1, -1}, k = 10
Salida: -1
Entrada: op[] = {-60, 65, -1, 14, -25}, k = 100000
Salida: 71391
Enfoque: Cuente la cantidad de veces que se pueden realizar todas las operaciones en el número k sin reducirlo para obtener el resultado. Luego actualice count = times * n donde n es el número de operaciones. Ahora, para las operaciones restantes, realice cada una de las operaciones una por una e incremente la cuenta . La primera operación cuando k se reduce a ≤ 0 , imprime la cuenta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int operations(int op[], int n, int k)
{
int i, count = 0;
// To store the normalized value
// of all the operations
int nVal = 0;
// Minimum possible value for
// a series of operations
int minimum = INT_MAX;
for (i = 0; i < n; i++)
{
nVal += op[i];
minimum = min(minimum , nVal);
// If k can be reduced with
// first (i + 1) operations
if ((k + nVal) <= 0)
return (i + 1);
}
// Impossible to reduce k
if (nVal >= 0)
return -1;
// Number of times all the operations
// can be performed on k without
// reducing it to <= 0
int times = (k - abs(minimum )) / abs(nVal);
// Perform operations
k = (k - (times * abs(nVal)));
count = (times * n);
// Final check
while (k > 0) {
for (i = 0; i < n; i++) {
k = k + op[i];
count++;
if (k <= 0)
break;
}
}
return count;
}
// Driver code
int main() {
int op[] = { -60, 65, -1, 14, -25 };
int n = sizeof(op)/sizeof(op[0]);
int k = 100000;
cout << operations(op, n, k) << endl;
}
// This code is contributed by Ryuga
Java
// Java implementation of the approach
class GFG {
static int operations(int op[], int n, int k)
{
int i, count = 0;
// To store the normalized value
// of all the operations
int nVal = 0;
// Minimum possible value for
// a series of operations
int min = Integer.MAX_VALUE;
for (i = 0; i < n; i++) {
nVal += op[i];
min = Math.min(min, nVal);
// If k can be reduced with
// first (i + 1) operations
if ((k + nVal) <= 0)
return (i + 1);
}
// Impossible to reduce k
if (nVal >= 0)
return -1;
// Number of times all the operations
// can be performed on k without
// reducing it to <= 0
int times = (k - Math.abs(min)) / Math.abs(nVal);
// Perform operations
k = (k - (times * Math.abs(nVal)));
count = (times * n);
// Final check
while (k > 0) {
for (i = 0; i < n; i++) {
k = k + op[i];
count++;
if (k <= 0)
break;
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int op[] = { -60, 65, -1, 14, -25 };
int n = op.length;
int k = 100000;
System.out.print(operations(op, n, k));
}
}
Python3
# Python3 implementation of the approach def operations(op, n, k): i, count = 0, 0 # To store the normalized value # of all the operations nVal = 0 # Minimum possible value for # a series of operations minimum = 10**9 for i in range(n): nVal += op[i] minimum = min(minimum , nVal) # If k can be reduced with # first (i + 1) operations if ((k + nVal) <= 0): return (i + 1) # Impossible to reduce k if (nVal >= 0): return -1 # Number of times all the operations # can be performed on k without # reducing it to <= 0 times = (k - abs(minimum )) // abs(nVal) # Perform operations k = (k - (times * abs(nVal))) count = (times * n) # Final check while (k > 0): for i in range(n): k = k + op[i] count += 1 if (k <= 0): break return count # Driver code op = [-60, 65, -1, 14, -25] n = len(op) k = 100000 print(operations(op, n, k)) # This code is contributed # by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
static int operations(int []op, int n, int k)
{
int i, count = 0;
// To store the normalized value
// of all the operations
int nVal = 0;
// Minimum possible value for
// a series of operations
int min = int.MaxValue;
for (i = 0; i < n; i++)
{
nVal += op[i];
min = Math.Min(min, nVal);
// If k can be reduced with
// first (i + 1) operations
if ((k + nVal) <= 0)
return (i + 1);
}
// Impossible to reduce k
if (nVal >= 0)
return -1;
// Number of times all the operations
// can be performed on k without
// reducing it to <= 0
int times = (k - Math.Abs(min)) / Math.Abs(nVal);
// Perform operations
k = (k - (times * Math.Abs(nVal)));
count = (times * n);
// Final check
while (k > 0)
{
for (i = 0; i < n; i++)
{
k = k + op[i];
count++;
if (k <= 0)
break;
}
}
return count;
}
// Driver code
static void Main()
{
int []op = { -60, 65, -1, 14, -25 };
int n = op.Length;
int k = 100000;
Console.WriteLine(operations(op, n, k));
}
}
// This code is contributed by mits
PHP
<?php
// PHP implementation of the approach
function operations($op, $n, $k)
{
$count = 0;
// To store the normalized value
// of all the operations
$nVal = 0;
// Minimum possible value for
// a series of operations
$minimum = PHP_INT_MAX;
for ($i = 0; $i < $n; $i++)
{
$nVal += $op[$i];
$minimum = min($minimum , $nVal);
// If k can be reduced with
// first (i + 1) operations
if (($k + $nVal) <= 0)
return ($i + 1);
}
// Impossible to reduce k
if ($nVal >= 0)
return -1;
// Number of times all the operations
// can be performed on k without
// reducing it to <= 0
$times = round(($k - abs($minimum )) /
abs($nVal));
// Perform operations
$k = ($k - ($times * abs($nVal)));
$count = ($times * $n);
// Final check
while ($k > 0)
{
for ($i = 0; $i < $n; $i++)
{
$k = $k + $op[$i];
$count++;
if ($k <= 0)
break;
}
}
return $count;
}
// Driver code
$op = array(-60, 65, -1, 14, -25 );
$n = sizeof($op);
$k = 100000;
echo operations($op, $n, $k);
// This code is contributed by ihritik
?>
Javascript
<script>
// Javascript implementation of the approach
function operations(op,n,k)
{
let i, count = 0;
// To store the normalized value
// of all the operations
let nVal = 0;
// Minimum possible value for
// a series of operations
let min = Number.MAX_VALUE;
for (i = 0; i < n; i++) {
nVal += op[i];
min = Math.min(min, nVal);
// If k can be reduced with
// first (i + 1) operations
if ((k + nVal) <= 0)
return (i + 1);
}
// Impossible to reduce k
if (nVal >= 0)
return -1;
// Number of times all the operations
// can be performed on k without
// reducing it to <= 0
let times = Math.floor((k - Math.abs(min)) / Math.abs(nVal));
// Perform operations
k = (k - (times * Math.abs(nVal)));
count = (times * n);
// Final check
while (k > 0) {
for (i = 0; i < n; i++) {
k = k + op[i];
count++;
if (k <= 0)
break;
}
}
return count;
}
// Driver code
let op=[-60, 65, -1, 14, -25];
let n = op.length;
let k = 100000;
document.write(operations(op, n, k));
// This code is contributed by unknown2108.
</script>
Producción:
71391
Complejidad de tiempo: O(n*k)
Espacio Auxiliar: O(1)