Given an integer N, the task is to count the minimum number of times N needs to be incremented or decremented by 2 to convert it to a perfect square.
Examples:
Input: N = 18
Output: 1
Explanation: N – 2 = 16(= 42). Therefore, a single decrement operation is required.Input: N = 15
Output: 3
Explanation:
N – 2 * 3 = 15 – 6 = 9 (= 32). Therefore, 3 decrement operations are required.
N + 2 * 5 = 25 (= 52). Therefore, 5 increment operations are required.
Therefore, minimum number of operations required is 3.
Approach: Follow the steps below to solve this problem:
- Count the total number of operations, say cntDecr required to make N as a perfect square number by decrementing the value of N by 2.
- Count the total number of operations, say cntIncr required to make N as a perfect square number by incrementing the value of N by 2.
- Finally, print the value of min(cntIncr, cntDecr).
Below is the implementation of the above approach.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of operations required to make// N a perfect squareint MinimumOperationReq(int N){ // Stores count of operations // by performing decrements int cntDecr = 0; // Stores value of N int temp = N; // Decrement the value of temp while (temp > 0) { // Stores square root of temp int X = sqrt(temp); // If temp is a perfect square if (X * X == temp) { break; } // Update temp temp = temp - 2; cntDecr += 1; } // Store count of operations // by performing increments int cntIncr = 0; // Increment the value of N while (true) { // Stores sqrt of N int X = sqrt(N); // If N is a perfect square if (X * X == N) { break; } // Update temp N = N + 2; cntIncr += 1; } // Return the minimum count return min(cntIncr, cntDecr);}// Driver Codeint main(){ int N = 15; cout << MinimumOperationReq(N); return 0;} |
Java
// Java program to implement // the above approach class GFG{ // Function to find the minimum number // of operations required to make // N a perfect square static int MinimumOperationReq(int N) { // Stores count of operations // by performing decrements int cntDecr = 0; // Stores value of N int temp = N; // Decrement the value of temp while (temp > 0) { // Stores square root of temp int X = (int)Math.sqrt(temp); // If temp is a perfect square if (X * X == temp) { break; } // Update temp temp = temp - 2; cntDecr += 1; } // Store count of operations // by performing increments int cntIncr = 0; // Increment the value of N while (true) { // Stores sqrt of N int X = (int)Math.sqrt(N); // If N is a perfect square if (X * X == N) { break; } // Update temp N = N + 2; cntIncr += 1; } // Return the minimum count return Math.min(cntIncr, cntDecr); }// Driver codepublic static void main (String args[]) { int N = 15; System.out.print(MinimumOperationReq(N)); } } // This code is contributed by ajaykr00kj |
Python3
# Python3 program to implement# the above approach# Function to find the minimum number# of operations required to make# N a perfect squaredef MinimumOperationReq(N): # Stores count of operations # by performing decrements cntDecr = 0; # Stores value of N temp = N; # Decrement the value of # temp while (temp > 0): # Stores square root of # temp X = int(pow(temp, 1 / 2)) # If temp is a perfect # square if (X * X == temp): break; # Update temp temp = temp - 2; cntDecr += 1; # Store count of operations # by performing increments cntIncr = 0; # Increment the value of N while (True): # Stores sqrt of N X = int(pow(N, 1 / 2)) # If N is a perfect # square if (X * X == N): break; # Update temp N = N + 2; cntIncr += 1; # Return the minimum # count return min(cntIncr, cntDecr);# Driver codeif __name__ == '__main__': N = 15; print(MinimumOperationReq(N));# This code is contributed by Rajput-Ji |
C#
// C# program to implement // the above approach using System;class GFG{ // Function to find the minimum number // of operations required to make // N a perfect square static int MinimumOperationReq(int N) { // Stores count of operations // by performing decrements int cntDecr = 0; // Stores value of N int temp = N; // Decrement the value of // temp while (temp > 0) { // Stores square root of temp int X = (int)Math.Sqrt(temp); // If temp is a perfect square if (X * X == temp) { break; } // Update temp temp = temp - 2; cntDecr += 1; } // Store count of operations // by performing increments int cntIncr = 0; // Increment the value of N while (true) { // Stores sqrt of N int X = (int)Math.Sqrt(N); // If N is a perfect square if (X * X == N) { break; } // Update temp N = N + 2; cntIncr += 1; } // Return the minimum count return Math.Min(cntIncr, cntDecr); }// Driver codepublic static void Main(String []args) { int N = 15; Console.Write(MinimumOperationReq(N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the minimum number// of operations required to make// N a perfect squarefunction MinimumOperationReq(N){ // Stores count of operations // by performing decrements let cntDecr = 0; // Stores value of N let temp = N; // Decrement the value of temp while (temp > 0) { // Stores square root of temp let X = Math.floor(Math.sqrt(temp)); // If temp is a perfect square if (X * X == temp) { break; } // Update temp temp = temp - 2; cntDecr += 1; } // Store count of operations // by performing increments let cntIncr = 0; // Increment the value of N while (true) { // Stores sqrt of N let X = Math.floor(Math.sqrt(N)); // If N is a perfect square if (X * X == N) { break; } // Update temp N = N + 2; cntIncr += 1; } // Return the minimum count return Math.min(cntIncr, cntDecr);} // Driver Code let N = 15; document.write(MinimumOperationReq(N)); </script> |
Output
3
Time Complexity: O(N * log2(N))
Auxiliary Space: O(1)
Efficient Approach:-
- If we think that from a odd number we can react at odd squares only by adding 2 or by subtracting 2
- So we will do two cases for odd and even
- In both of the cases we will find out the nearest small and greater square than N.
- And find the difference between then
- As we are taking +2 or -2 steps then the steps will be difference/2.
- At the end we will take minimum steps from +2 or -2
Implementation:-
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number// of operations required to make// N a perfect squareint MinimumOperationReq(int N){ int cntIncr = 0, cntDecr = 0; // if N is odd then we can reach at odd squares only if (N % 2) { // getting the nearest square small than N int X = sqrt(N); // because we can reach at odd number square only if (X % 2 == 0) X--; // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only odd nnumber square if (X % 2 == 0) X++; // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // we can reach at even squares only else { // getting the nearest square small than N int X = sqrt(N); // because we can reach at even number square only if (X % 2) X--; // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only even nnumber square if (X % 2) X++; // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // Return the minimum count return min(cntIncr, cntDecr);}// Driver Codeint main(){ int N = 15; cout << MinimumOperationReq(N); return 0;}// This code contributed by shubhamrajput6156 |
Java
// Java equivalent of the above C++ programimport java.lang.Math;public class Main{ // Function to find the minimum number // of operations required to make // N a perfect square public static int MinimumOperationReq(int N) { int cntIncr = 0, cntDecr = 0; // if N is odd then we can reach at odd squares only if (N % 2 != 0) { // getting the nearest square small than N int X = (int)Math.sqrt(N); // because we can reach at odd number square only if (X % 2 == 0) X--; // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only odd nnumber square if (X % 2 == 0) X++; // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // we can reach at even squares only else { // getting the nearest square small than N int X = (int)Math.sqrt(N); // because we can reach at even number square only if (X % 2 != 0) X--; // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only even nnumber square if (X % 2 != 0) X++; // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // Return the minimum count return Math.min(cntIncr, cntDecr); } // Driver code public static void main(String[] args) { int N = 15; System.out.println(MinimumOperationReq(N)); }} |
Python3
# C++ program to implement# the above approachimport math# Function to find the minimum number# of operations required to make# N a perfect squaredef MinimumOperationReq(N): cntIncr = 0 cntDecr = 0 # if N is odd then we can reach at odd squares only if N % 2: # getting the nearest square small than N X = int(math.sqrt(N)) # because we can reach at odd number square only if X % 2 == 0: X -= 1 # getting difference between near square and N diff = N - X * X # getting steps to reach by N-2 cntDecr = diff // 2 X += 1 # because we can reach only odd nnumber square if X % 2 == 0: X += 1 # getting the difference between upper square than # N diff = X * X - N cntIncr = diff // 2 # we can reach at even squares only else: # getting the nearest square small than N X = int(math.sqrt(N)) # because we can reach at even number square only if X % 2: X -= 1 # getting difference between near square and N diff = N - X * X # getting steps to reach by N-2 cntDecr = diff // 2 X += 1 # because we can reach only even nnumber square if X % 2: X += 1 # getting the difference between upper square than # N diff = X * X - N cntIncr = diff // 2 # Return the minimum count return min(cntIncr, cntDecr)# Driver Codeif __name__ == "__main__": N = 15 print(MinimumOperationReq(N)) |
C#
// C# program to implement// the above approachusing System;// Function to find the minimum number// of operations required to make// N a perfect squarepublic class GFG{ public static int MinimumOperationReq(int N) { int cntIncr = 0; int cntDecr = 0; // if N is odd then we can reach at odd squares only if ((N % 2) != 0) { // getting the nearest square small than N double _X = Math.Sqrt(N); int X = Convert.ToInt32(_X); // because we can reach at odd number square only if (X % 2 == 0) { X--; } // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only odd nnumber square if (X % 2 == 0) { X++; } // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // we can reach at even squares only else { // getting the nearest square small than N double _X = Math.Sqrt(N); int X = Convert.ToInt32(_X); // because we can reach at even number square only if ((X % 2) != 0) { X--; } // getting difference between near square and N int diff = N - X * X; // getting steps to reach by N-2 cntDecr = diff / 2; X++; // because we can reach only even nnumber square if ((X % 2) != 0) { X++; } // getting the difference between upper square than // N diff = X * X - N; cntIncr = diff / 2; } // Return the minimum count return Math.Min(cntIncr, cntDecr); } // Driver Code internal static void Main() { int N = 15; Console.Write(MinimumOperationReq(N)); }}//this code is contributed by bhardwajji |
Javascript
// Function to find the minimum number// of operations required to make// N a perfect squarefunction MinimumOperationReq(N) { let cntIncr = 0; let cntDecr = 0; // if N is odd then we can reach at odd squares only if (N % 2) { // getting the nearest square small than N let X = Math.floor(Math.sqrt(N)); // because we can reach at odd number square only if (X % 2 == 0) { X -= 1; } // getting difference between near square and N let diff = N - X * X; // getting steps to reach by N-2 cntDecr = Math.floor(diff / 2); X += 1; // because we can reach only odd number square if (X % 2 == 0) { X += 1; } // getting the difference between upper square than N diff = X * X - N; cntIncr = Math.floor(diff / 2); } // we can reach at even squares only else { // getting the nearest square small than N let X = Math.floor(Math.sqrt(N)); // because we can reach at even number square only if (X % 2) { X -= 1; } // getting difference between near square and N let diff = N - X * X; // getting steps to reach by N-2 cntDecr = Math.floor(diff / 2); X += 1; // because we can reach only even number square if (X % 2) { X += 1; } // getting the difference between upper square than N diff = X * X - N; cntIncr = Math.floor(diff / 2); } // Return the minimum count return Math.min(cntIncr, cntDecr);}// Driver Codelet N = 15;console.log(MinimumOperationReq(N)); |
Output
3
Time Complexity:- O(LogN)
Auxiliary Space:- 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!
