Dado un número entero N , la tarea es encontrar el número mínimo de divisiones requeridas para reducir el número a 1 cuando las divisiones siguen los criterios dados:
- Elija dos enteros X e Y tales que X+Y sea par.
- Reemplace N con N/X Y donde X Y es un divisor de N
Nota: si es imposible reducir N a 1, devuelva -1.
Ejemplos:
Entrada: N = 35
Salida: 1
Explicación: Seleccione X = 35 e Y = 1. X+Y = 36 que es par,
y X Y = 35 es un divisor de N = 35, por lo que esta es una opción válida.Entrada: 44
Salida: 2
Enfoque: El problema se puede resolver con base en la siguiente observación matemática:
- Si N es impar, X puede elegirse como X = N e Y = 1 . Entonces X Y = X = N y también X + Y = X + 1 = par.
- Si N es par, N se puede escribir como N = 2 p * X , donde p es cualquier número entero y X es un número impar (puede ser 1).
- Si p es impar, nunca es posible reducir el número a 1 ya que 2 + p siempre será impar.
- De lo contrario, se necesitarán 2 movimientos para reducir el número a 1: un paso para reducir el número a X y otro paso para reducirlo de X a 1.
- Si X = 1, entonces no se necesita un segundo paso y 1 paso será suficiente.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Encuentra si el número es par o impar .
- Si el número es par entonces:
- Si 2 se eleva a una potencia impar, entonces la respuesta no es posible.
- De lo contrario, obtenga el número mínimo de pasos como se muestra en la observación anterior.
- Si el número es impar, solo se necesita un paso.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find
// the minimum number of moves
int minStep(long N)
{
if (N == 1)
return 0;
// If number input by user is odd
else if (N % 2 == 1)
return 1;
else {
float X;
int count = 0;
// Finding square root of
// integer input by user
X = sqrt(N);
// Is perfect square
if (X == round(X)) {
return 1;
}
else {
// Checking number is divisible by 2
while (N % 2 == 0) {
N /= 2;
count++;
}
// Check value of count is
// odd or even
if (count % 2 == 0)
return 2;
else
return -1;
}
}
}
// Driver code
int main()
{
long N = 35;
// Function call
cout << (minStep(N));
return 0;
}
// This code is contributed by rakeshsahni
C
// C code to implement the approach
#include <math.h>
#include <stdio.h>
// Function to find
// the minimum number of moves
int minStep(long N)
{
if (N == 1)
return 0;
// If number input by user is odd
else if (N % 2 == 1)
return 1;
else {
float X;
int count = 0;
// Finding square root of
// integer input by user
X = sqrt(N);
// Is perfect square
if (X == round(X)) {
return 1;
}
else {
// Checking number is divisible by 2
while (N % 2 == 0) {
N /= 2;
count++;
}
// Check value of count is
// odd or even
if (count % 2 == 0)
return 2;
else
return -1;
}
}
}
// Driver code
int main()
{
long N = 35;
// Function call
printf("%d",minStep(N));
return 0;
}
// This code is contributed by Aarohi Rai
Java
// java code to implement the approach
import java.util.*;
class GFG {
// Function to find
// the minimum number of moves
public static int minStep(long N)
{
if (N == 1)
return 0;
// If number input by user is odd
else if (N % 2 == 1)
return 1;
else {
Double X;
int count = 0;
// Finding square root of
// integer input by user
X = Math.sqrt(N);
// Is perfect square
if (X == Math.round(X)) {
return 1;
}
else {
// Checking number is divisible by 2
while (N % 2 == 0) {
N /= 2;
count++;
}
// Check value of count is
// odd or even
if (count % 2 == 0)
return 2;
else
return -1;
}
}
}
// Driver code
public static void main(String[] args)
{
long N = 35;
// Function call
System.out.println(minStep(N));
}
}
Python3
# Python code to implement the approach import math # Function to find # the minimum number of moves def minStep(N): if N == 1: return 0 # If number input by user is odd elif N % 2 == 1: return 1 else: X = 0.0 count = 0 # Finding square root of # integer input by user X = math.sqrt(N) # Is perfect square if X == round(X): return 1 else: # Checking number is divisible by 2 while N % 2 == 0: N /= 2 count += 1 # Check value of count is # odd or even if count % 2 == 0: return 2 else: return -1 # Driver code if __name__ == "__main__": N = 35 # Function call print(minStep(N)) # This code is contributed by Rohit Pradhan
C#
// C# code to implement the approach
using System;
class GFG {
// Function to find
// the minimum number of moves
static int minStep(long N)
{
if (N == 1)
return 0;
// If number input by user is odd
else if (N % 2 == 1)
return 1;
else {
double X = 0;
int count = 0;
// Finding square root of
// integer input by user
X = Math.Sqrt(N);
// Is perfect square
if (X == Math.Round(X)) {
return 1;
}
else {
// Checking number is divisible by 2
while (N % 2 == 0) {
N /= 2;
count++;
}
// Check value of count is
// odd or even
if (count % 2 == 0)
return 2;
else
return -1;
}
}
}
// Driver code
public static void Main()
{
long N = 35;
// Function call
Console.WriteLine(minStep(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code to implement the approach
// Function to find
// the minimum number of moves
function minStep(N)
{
if (N == 1)
return 0;
// If number input by user is odd
else if (N % 2 == 1)
return 1;
else {
let X;
let count = 0;
// Finding square root of
// integer input by user
X = Math.sqrt(N);
// Is perfect square
if (X == Math.round(X)) {
return 1;
}
else {
// Checking number is divisible by 2
while (N % 2 == 0) {
N = Math.floor(N/2);
count++;
}
// Check value of count is
// odd or even
if (count % 2 == 0)
return 2;
else
return -1;
}
}
}
// Driver code
let N = 35;
// Function call
document.write(minStep(N),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
1
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aarohirai2616 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA