Dado un número entero N , la tarea es contar el número mínimo de veces que N debe incrementarse o disminuirse en 2 para convertirlo en un cuadrado perfecto .
Ejemplos:
Entrada: N = 18
Salida: 1
Explicación: N – 2 = 16(= 4 2 ). Por lo tanto, se requiere una sola operación de decremento.Entrada: N = 15
Salida: 3
Explicación:
N – 2 * 3 = 15 – 6 = 9 (= 3 2 ). Por lo tanto, se requieren 3 operaciones de decremento.
N + 2 * 5 = 25 (= 5 2 ). Por lo tanto, se requieren 5 operaciones de incremento.
Por lo tanto, el número mínimo de operaciones requeridas es 3.
Enfoque: siga los pasos a continuación para resolver este problema:
- Cuente el número total de operaciones, digamos cntDecr requeridas para hacer que N sea un número cuadrado perfecto al disminuir el valor de N en 2 .
- Cuente el número total de operaciones, digamos cntIncr requeridas para hacer que N sea un número cuadrado perfecto incrementando el valor de N en 2 .
- Finalmente, imprime el valor de min(cntIncr, cntDecr) .
A continuación se muestra la implementación del enfoque anterior.
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 square
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 = 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 Code
int 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 code
public 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 square def 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 code if __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 code
public 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 square
function 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>
Producción:
3
Complejidad de tiempo: O(N * log 2 (N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA