Dado un elemento entero ‘N’, la tarea es encontrar el número mínimo de operaciones que deben realizarse para que ‘N’ sea igual a 1.
Las operaciones permitidas que se pueden realizar son:
- Disminuya N en 1.
- Incremente N en 1.
- Si N es múltiplo de 3, puedes dividir N por 3.
Ejemplos:
Entrada: N = 4
Salida: 2
4 – 1 = 3
3 / 3 = 1
El número mínimo de operaciones requeridas es 2.Entrada: N = 8
Salida: 3
8 + 1 = 9
9 / 3 = 3
3 / 3 = 1
El número mínimo de operaciones requeridas es 3.
Acercarse:
- Si el número es múltiplo de 3, se divide por 3.
- Si el número módulo 3 es 1, decrementarlo en 1.
- Si el número módulo 3 es 2, increméntelo en 1.
- Hay una excepción cuando el número es igual a 2, en este caso el número debe ser decrementado en 1.
- Repita los pasos anteriores hasta que el número sea mayor que 1 e imprima el recuento de operaciones realizadas al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
int count_minimum_operations(long long n)
{
// To stores the total number of
// operations to be performed
int count = 0;
while (n > 1) {
// if n is divisible by 3
// then reduce it to n / 3
if (n % 3 == 0)
n /= 3;
// if n modulo 3 is 1
// decrement it by 1
else if (n % 3 == 1)
n--;
else {
if (n == 2)
n--;
// if n modulo 3 is 2
// then increment it by 1
else
n++;
}
// update the counter
count++;
}
return count;
}
// Driver code
int main()
{
long long n = 4;
long long ans = count_minimum_operations(n);
cout<<ans<<endl;
return 0;
}
// This code is contributed by mits
Java
// Java implementation of above approach
class GFG {
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
static int count_minimum_operations(long n)
{
// To stores the total number of
// operations to be performed
int count = 0;
while (n > 1) {
// if n is divisible by 3
// then reduce it to n / 3
if (n % 3 == 0)
n /= 3;
// if n modulo 3 is 1
// decrement it by 1
else if (n % 3 == 1)
n--;
else {
if (n == 2)
n--;
// if n modulo 3 is 2
// then increment it by 1
else
n++;
}
// update the counter
count++;
}
return count;
}
// Driver code
public static void main(String[] args)
{
long n = 4;
long ans = count_minimum_operations(n);
System.out.println(ans);
}
}
Python3
# Python3 implementation of above approach # Function that returns the minimum # number of operations to be performed # to reduce the number to 1 def count_minimum_operations(n): # To stores the total number of # operations to be performed count = 0 while (n > 1) : # if n is divisible by 3 # then reduce it to n / 3 if (n % 3 == 0): n //= 3 # if n modulo 3 is 1 # decrement it by 1 elif (n % 3 == 1): n -= 1 else : if (n == 2): n -= 1 # if n modulo 3 is 2 # then increment it by 1 else: n += 1 # update the counter count += 1 return count # Driver code if __name__ =="__main__": n = 4 ans = count_minimum_operations(n) print (ans) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach
using System;
public class GFG{
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
static int count_minimum_operations(long n)
{
// To stores the total number of
// operations to be performed
int count = 0;
while (n > 1) {
// if n is divisible by 3
// then reduce it to n / 3
if (n % 3 == 0)
n /= 3;
// if n modulo 3 is 1
// decrement it by 1
else if (n % 3 == 1)
n--;
else {
if (n == 2)
n--;
// if n modulo 3 is 2
// then increment it by 1
else
n++;
}
// update the counter
count++;
}
return count;
}
// Driver code
static public void Main (){
long n = 4;
long ans = count_minimum_operations(n);
Console.WriteLine(ans);
}
}
PHP
<?php
// PHP implementation of above approach
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
function count_minimum_operations($n)
{
// To stores the total number of
// operations to be performed
$count = 0;
while ($n > 1)
{
// if n is divisible by 3
// then reduce it to n / 3
if ($n % 3 == 0)
$n /= 3;
// if n modulo 3 is 1
// decrement it by 1
else if ($n % 3 == 1)
$n--;
else
{
if ($n == 2)
$n--;
// if n modulo 3 is 2
// then increment it by 1
else
$n++;
}
// update the counter
$count++;
}
return $count;
}
// Driver code
$n = 4;
$ans = count_minimum_operations($n);
echo $ans, "\n";
// This code is contributed by akt_mit
?>
Javascript
<script>
// Javascript implementation of above approach
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
function count_minimum_operations(n)
{
// To stores the total number of
// operations to be performed
let count = 0;
while (n > 1) {
// if n is divisible by 3
// then reduce it to n / 3
if (n % 3 == 0)
n /= 3;
// if n modulo 3 is 1
// decrement it by 1
else if (n % 3 == 1)
n--;
else {
if (n == 2)
n--;
// if n modulo 3 is 2
// then increment it by 1
else
n++;
}
// update the counter
count++;
}
return count;
}
let n = 4;
let ans = count_minimum_operations(n);
document.write(ans);
</script>
Producción
2
Complejidad de tiempo: O(n), donde n representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Enfoque recursivo: El enfoque recursivo es similar al enfoque utilizado anteriormente.
A continuación se muestra la implementación:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
int count_minimum_operations(long long n)
{
// Base cases
if (n == 2) {
return 1;
}
else if (n == 1) {
return 0;
}
if (n % 3 == 0) {
return 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
return 1 + count_minimum_operations(n - 1);
}
else {
return 1 + count_minimum_operations(n + 1);
}
}
// Driver code
int main()
{
long long n = 4;
long long ans = count_minimum_operations(n);
cout << ans << endl;
return 0;
}
// This code is contributed by koulick_sadhu
Java
// Java implementation of above approach
import java.util.*;
class GFG{
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
public static int count_minimum_operations(int n)
{
// Base cases
if (n == 2)
{
return 1;
}
else if (n == 1)
{
return 0;
}
if (n % 3 == 0)
{
return 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1)
{
return 1 + count_minimum_operations(n - 1);
}
else
{
return 1 + count_minimum_operations(n + 1);
}
}
// Driver code
public static void main(String []args)
{
int n = 4;
int ans = count_minimum_operations(n);
System.out.println(ans);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of above approach # Function that returns the minimum # number of operations to be performed # to reduce the number to 1 def count_minimum_operations(n): # Base cases if (n == 2): return 1 elif (n == 1): return 0 if (n % 3 == 0): return 1 + count_minimum_operations(n / 3) elif (n % 3 == 1): return 1 + count_minimum_operations(n - 1) else: return 1 + count_minimum_operations(n + 1) # Driver Code n = 4 ans = count_minimum_operations(n) print(ans) # This code is contributed by divyesh072019
C#
// C# implementation of above approach
using System;
class GFG {
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
static int count_minimum_operations(int n)
{
// Base cases
if (n == 2) {
return 1;
}
else if (n == 1) {
return 0;
}
if (n % 3 == 0) {
return 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
return 1 + count_minimum_operations(n - 1);
}
else {
return 1 + count_minimum_operations(n + 1);
}
}
// Driver code
static void Main() {
int n = 4;
int ans = count_minimum_operations(n);
Console.WriteLine(ans);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript implementation of above approach
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
function count_minimum_operations(n)
{
// Base cases
if (n == 2) {
return 1;
}
else if (n == 1) {
return 0;
}
if (n % 3 == 0) {
return 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
return 1 + count_minimum_operations(n - 1);
}
else {
return 1 + count_minimum_operations(n + 1);
}
}
let n = 4;
let ans = count_minimum_operations(n);
document.write(ans);
// This code is contributed by suresh07.
</script>
Producción
2
Complejidad de tiempo: O(n), donde n representa el entero dado.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Otro método (eficiente) :
DP usando memorización (enfoque de arriba hacia abajo)
Podemos evitar el trabajo repetido almacenando las operaciones realizadas calculadas hasta el momento. Solo necesitamos almacenar todos los valores en una array.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
int static dp[1001];
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
int count_minimum_operations(long long n)
{
// Base cases
if (n == 2) {
return 1;
}
if (n == 1) {
return 0;
}
if(dp[n] != -1)
{
return dp[n];
}
if (n % 3 == 0) {
dp[n] = 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
dp[n] = 1 + count_minimum_operations(n - 1);
}
else {
dp[n] = 1 + count_minimum_operations(n + 1);
}
return dp[n];
}
// Driver code
int main()
{
long long n = 4;
memset(dp, -1, sizeof(dp));
long long ans = count_minimum_operations(n);
cout << ans << endl;
return 0;
}
// This code is contributed by Samim Hossain Mondal
Java
// Java implementation of above approach
import java.util.*;
public class GFG
{
static int []dp = new int[1001];
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
public static int count_minimum_operations(int n)
{
// Base cases
if (n == 2)
{
return 1;
}
else if (n == 1)
{
return 0;
}
if(dp[n] != -1)
{
return dp[n];
}
if (n % 3 == 0) {
dp[n] = 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
dp[n] = 1 + count_minimum_operations(n - 1);
}
else {
dp[n] = 1 + count_minimum_operations(n + 1);
}
return dp[n];
}
// Driver code
public static void main(String []args)
{
int n = 4;
for(int i = 0; i < 1001; i++) {
dp[i] = -1;
}
int ans = count_minimum_operations(n);
System.out.println(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Python
# Python3 implementation of above approach # Function that returns the minimum # number of operations to be performed # to reduce the number to 1 dp = [-1 for i in range(1001)] def count_minimum_operations(n): # Base cases if (n == 2): return 1 elif (n == 1): return 0 if(dp[n] != -1): return dp[n] elif (n % 3 == 0): dp[n] = 1 + count_minimum_operations(n / 3) elif (n % 3 == 1): dp[n] = 1 + count_minimum_operations(n - 1) else: dp[n] = 1 + count_minimum_operations(n + 1) return dp[n] # Driver Code n = 4 ans = count_minimum_operations(n) print(ans) # This code is contributed by Samim Hossain Mondal
C#
// C# implementation of above approach
using System;
class GFG
{
static int []dp = new int[1001];
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
public static int count_minimum_operations(int n)
{
// Base cases
if (n == 2)
{
return 1;
}
else if (n == 1)
{
return 0;
}
if(dp[n] != -1)
{
return dp[n];
}
if (n % 3 == 0) {
dp[n] = 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
dp[n] = 1 + count_minimum_operations(n - 1);
}
else {
dp[n] = 1 + count_minimum_operations(n + 1);
}
return dp[n];
}
// Driver code
public static void Main()
{
int n = 4;
for(int i = 0; i < 1001; i++) {
dp[i] = -1;
}
int ans = count_minimum_operations(n);
Console.Write(ans);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
let dp = [];
// Function that returns the minimum
// number of operations to be performed
// to reduce the number to 1
function count_minimum_operations(n)
{
// Base cases
if (n == 2) {
return 1;
}
if (n == 1) {
return 0;
}
if(dp[n] != -1)
{
return dp[n];
}
if (n % 3 == 0) {
dp[n] = 1 + count_minimum_operations(n / 3);
}
else if (n % 3 == 1) {
dp[n] = 1 + count_minimum_operations(n - 1);
}
else {
dp[n] = 1 + count_minimum_operations(n + 1);
}
return dp[n];
}
// Driver Code
// Input Nth term
let n = 4;
for(let i = 0; i < 1001; i++) {
dp[i] = -1;
}
let ans = count_minimum_operations(n);
document.write(ans);
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
2
Complejidad de tiempo: O(n), donde n representa el entero dado.
Espacio Auxiliar: O(n), ya que se han tomado n espacios extra.
Publicación traducida automáticamente
Artículo escrito por AmanKumarSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA