Número obtenido al reducir la suma de dígitos de 2N en un solo dígito

Dado un entero positivo N , la tarea es encontrar el dígito único obtenido después de sumar recursivamente los dígitos de 2 ^N hasta que quede un solo dígito.

Ejemplos:

Entrada: N = 6
Salida: 1
Explicación: 
2 ⁶ = 64. Suma de dígitos = 10.
Ahora, Suma de dígitos = 10. Por lo tanto, la suma es 1.

Entrada: N = 10
Salida: 7
Explicación: 2 ¹⁰ = 1024. Suma de dígitos = 7.

Enfoque ingenuo: el enfoque más simple para resolver el problema es calcular el valor de 2 ^N y luego seguir calculando la suma de los dígitos del número hasta que la suma se reduzca a un solo dígito. 

Complejidad de tiempo: O(log(2 ^N ))
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

Después de realizar la operación para diferentes valores de N , se puede observar que el valor se repite cada 6 números de la siguiente manera:

• Si N % 6 = 0, entonces la suma de un solo dígito será igual a 1.
• Si N % 6 = 1, entonces la suma de un solo dígito será igual a 2.
• Si N % 6 = 2, entonces la suma de un solo dígito será igual a 4.
• Si N % 6 = 3, entonces la suma de un solo dígito será igual a 8.
• Si N % 6 = 4, entonces la suma de un solo dígito será igual a 7.
• Si N % 6 = 5, entonces la suma de un solo dígito será igual a 5.

Siga los pasos a continuación para resolver el problema:

• Si N % 6 es 0 , imprima 1 .
• De lo contrario, si N % 6 es 1 , imprima 2 .
• De lo contrario, si N % 6 es 2 , imprima 7 .
• De lo contrario, si N % 6 es 3 , imprima 8 .
• De lo contrario, si N % 6 es 4 , imprima 7 .
• De lo contrario, si N % 6 es 5 , imprima 5 .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number obtained
// by reducing sum of digits of 2 ^ N
// into a single digit
int findNumber(int N)
{
    // Stores answers for
    // different values of N
    int ans[6] = { 1, 2, 4, 8, 7, 5 };
 
    return ans[N % 6];
}
 
// Driver Code
int main()
{
    int N = 6;
    cout << findNumber(N) << endl;
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
  
// Function to find the number obtained
// by reducing sum of digits of 2 ^ N
// into a single digit
static int findNumber(int N)
{
     
    // Stores answers for
    // different values of N
    int []ans = {1, 2, 4, 8, 7, 5};
 
    return ans[N % 6];
}
 
// Driver Code
public static void main(String args[])
{
    int N = 6;
     
    System.out.println(findNumber(N));
}
}
 
// This code is contributed by ipg2016107

# Python3 program for the above approach
 
# Function to find the number obtained
# by reducing sum of digits of 2 ^ N
# into a single digit
def findNumber(N):
 
    # Stores answers for
    # different values of N
    ans = [ 1, 2, 4, 8, 7, 5 ]
 
    return ans[N % 6]
 
# Driver Code
if __name__ == "__main__":
  
    N = 6
     
    print (findNumber(N))
 
# This code is contributed by ukasp

// C# program for the above approach
using System;
 
class GFG{
  
// Function to find the number obtained
// by reducing sum of digits of 2 ^ N
// into a single digit
static int findNumber(int N)
{
     
    // Stores answers for
    // different values of N
    int []ans = {1, 2, 4, 8, 7, 5};
 
    return ans[N % 6];
}
 
// Driver Code
public static void Main()
{
    int N = 6;
     
    Console.WriteLine(findNumber(N));
}
}
 
// This code is contributed by mohit kumar 29

<script>
// JavaScript program for the above approach
 
// Function to find the number obtained
// by reducing sum of digits of 2 ^ N
// into a single digit
function findNumber(N)
{
 
    // Stores answers for
    // different values of N
    let ans = [ 1, 2, 4, 8, 7, 5 ];
    return ans[N % 6];
}
 
// Driver Code
    let N = 6;
    document.write(findNumber(N) + "<br>");
 
// This code is contributed by Surbhi Tyagi.
</script>

1

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)