Given two integers N and K, denoting the number of operations allowed and the number that needs to be obtained after performing N operations respectively. Consider a value S, initially 0, the task is to convert S to K by performing the following operations N times in any manner:
- Subtract 1 from S.
- Add P + 1 to S, where P is the number added previously(initially 0).
If it is not possible to convert S to K, print -1. Otherwise, print the number of decrement operations are required to be performed.
Note: S must be positive after every operation performed.
Examples:
Input: N = 5, K = 4
Output: 2
Explanation:
The order of the N operations performed:
Step 1: Adding 1 to S converts S = 1
Step 2: Adding 2 to S converts S = 3
Step 3: Subtracting 1 from S converts S = 2
Step 4: Adding 3 to S converts S = 5
Step 5: Subtracting 1 from S converts S = 4.
Since S is equal to K after N(= 5) operations, the answer is 2 as 2 decrement operations are performed.Input: N = 10, K = 3
Output: -1
Naive Approach: The simplest idea is to iterate a loop over the range [1, N] and check for the following conditions:
and i + K = N.
If there exists any value of i from the range [1, N] satisfying the above conditions, then print the value of i. Otherwise, print “-1”.
Time Complexity: O(N), where N is the maximum number of steps allowed.
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Binary Search. Below are the steps:
- Initialize two variables start as 0 and end as N.
- Find the middle index of the above two variables by taking the average of start and end.
- Check if we can have a mid number of steps of Type 1. If yes, then print mid and stop the iteration.
- Else update start or end according to the results we get by checking mid and repeat from step 2.
- If there doesn’t exist any mid satisfying the given condition then print “-1”.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether m number// of steps of type 1 are valid or notint isValid(int n, int m, int k){ // If m and n are the count of operations // of type 1 and type 2 respectively, // then n - m operations are performed int step2 = n - m; // Find the value of S after step 2 int cnt = (step2 * (step2 + 1)) / 2; // If m steps of type 1 is valid if (cnt - m == k) return 0; if (cnt - m > k) return 1; return -1;}// Function to find the number of// operations of type 1 requiredvoid countOfOperations(int n, int k){ int start = 0, end = n; bool ok = 1; // Iterate over the range while (start <= end) { // Find the value of mid int mid = (start + end) / 2; // Check if m steps of type 1 // are valid or not int temp = isValid(n, mid, k); // If mid is the valid // number of steps if (temp == 0) { ok = 0; cout << mid; break; } else if (temp == 1) { start = mid + 1; } else { end = mid - 1; } } // If no valid number // of steps exist if (ok) cout << "-1";}// Driver Codeint main(){ // Given and N, K int N = 5, K = 4; // Function Call countOfOperations(N, K); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check whether m number// of steps of type 1 are valid or notstatic int isValid(int n, int m, int k){ // If m and n are the count of operations // of type 1 and type 2 respectively, // then n - m operations are performed int step2 = n - m; // Find the value of S after step 2 int cnt = (step2 * (step2 + 1)) / 2; // If m steps of type 1 is valid if (cnt - m == k) return 0; if (cnt - m > k) return 1; return -1;}// Function to find the number of// operations of type 1 requiredstatic void countOfOperations(int n, int k){ int start = 0, end = n; boolean ok = true; // Iterate over the range while (start <= end) { // Find the value of mid int mid = (start + end) / 2; // Check if m steps of type 1 // are valid or not int temp = isValid(n, mid, k); // If mid is the valid // number of steps if (temp == 0) { ok = false; System.out.print(mid); break; } else if (temp == 1) { start = mid + 1; } else { end = mid - 1; } } // If no valid number // of steps exist if (ok) System.out.print("-1");}// Driver Codepublic static void main(String[] args){ // Given and N, K int N = 5, K = 4; // Function call countOfOperations(N, K);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach # Function to check whether m number # of steps of type 1 are valid or notdef isValid(n, m, k): # If m and n are the count of operations # of type 1 and type 2 respectively, # then n - m operations are performed step2 = n - m # Find the value of S after step 2 cnt = (step2 * (step2 + 1)) // 2 # If m steps of type 1 is valid if (cnt - m == k): return 0 if (cnt - m > k): return 1 return -1# Function to find the number of# operations of type 1 requireddef countOfOperations(n, k): start = 0 end = n ok = 1 # Iterate over the range while(start <= end): # Find the value of mid mid = (start + end) // 2 # Check if m steps of type 1 # are valid or not temp = isValid(n, mid, k) # If mid is the valid # number of steps if (temp == 0): ok = 0 print(mid) break elif (temp == 1): start = mid + 1 else: end = mid - 1 # If no valid number # of steps exist if (ok): print("-1")# Driver Code# Given and N, KN = 5K = 4# Function callcountOfOperations(N, K)# This code is contributed by Shivam Singh |
C#
// C# program for // the above approachusing System;class GFG{// Function to check // whether m number of steps // of type 1 are valid or notstatic int isValid(int n, int m, int k){ // If m and n are the // count of operations // of type 1 and type 2 // respectively, then n - m // operations are performed int step2 = n - m; // Find the value of S // after step 2 int cnt = (step2 * (step2 + 1)) / 2; // If m steps of // type 1 is valid if (cnt - m == k) return 0; if (cnt - m > k) return 1; return -1;}// Function to find the // number of operations // of type 1 required static void countOfOperations(int n, int k){ int start = 0, end = n; bool ok = true; // Iterate over the range while (start <= end) { // Find the value of mid int mid = (start + end) / 2; // Check if m steps of type 1 // are valid or not int temp = isValid(n, mid, k); // If mid is the valid // number of steps if (temp == 0) { ok = false; Console.Write(mid); break; } else if (temp == 1) { start = mid + 1; } else { end = mid - 1; } } // If no valid number // of steps exist if (ok) Console.Write("-1");}// Driver Codepublic static void Main(String[] args){ // Given and N, K int N = 5, K = 4; // Function call countOfOperations(N, K);}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Function to check whether m number// of steps of type 1 are valid or notfunction isValid(n, m, k){ // If m and n are the count of operations // of type 1 and type 2 respectively, // then n - m operations are performed var step2 = n - m; // Find the value of S after step 2 var cnt = parseInt((step2 * (step2 + 1)) / 2); // If m steps of type 1 is valid if (cnt - m == k) return 0; if (cnt - m > k) return 1; return -1;}// Function to find the number of// operations of type 1 requiredfunction countOfOperations(n, k){ var start = 0, end = n; var ok = 1; // Iterate over the range while (start <= end) { // Find the value of mid var mid = parseInt((start + end) / 2); // Check if m steps of type 1 // are valid or not var temp = isValid(n, mid, k); // If mid is the valid // number of steps if (temp == 0) { ok = 0; document.write( mid); break; } else if (temp == 1) { start = mid + 1; } else { end = mid - 1; } } // If no valid number // of steps exist if (ok) document.write( "-1");}// Driver Code// Given and N, Kvar N = 5, K = 4;// Function CallcountOfOperations(N, K);</script> |
Output:
2
Time Complexity: O(log2N), where N is the given steps
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
