Count the number of operations required to reduce the given number
Given an integer k and an array op[], in a single operation op[0] will be added to k and then in the second operation k = k + op[1] and so on in a circular manner until k > 0. The task is to print the operation number in which k will be reduced to ? 0. If it impossible to reduce k with the given operations then print -1.
Examples:
Input: op[] = {-60, 10, -100}, k = 100
Output: 3
Operation 1: 100 – 60 = 40
Operation 2: 40 + 10 = 50
Operation 3: 50 – 100 = -50
Input: op[] = {1, 1, -1}, k = 10
Output: -1
Input: op[] = {-60, 65, -1, 14, -25}, k = 100000
Output: 71391
Approach: Count the number of times all the operations can be performed on the number k without actually reducing it to get the result. Then update count = times * n where n is the number of operations. Now, for the remaining operations perform each of the operation one by one and increment count. The first operation when k is reduced to ? 0, print the count.
Below is the implementation of the above approach:
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> |
71391
Time Complexity: O(n*k)
Auxiliary Space: O(1)