Given a positive integer N, the task is to find the single digit obtained after recursively adding the digits of 2N until a single digit remains.
Examples:
Input: N = 6
Output: 1
Explanation:
26 = 64. Sum of digits = 10.
Now, Sum of digits = 10. Therefore, sum is 1.Input: N = 10
Output: 7
Explanation: 210 = 1024. Sum of digits = 7.
Naive Approach: The simplest approach to solve the problem is to calculate the value of 2N and then, keep calculating the sum of digits of number until the sum reduces to a single digit.
Time Complexity: O(log(2N))
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
After performing the operation for different values of N, it can be observed that the value repeats after every 6 numbers in the following manner:
- If N % 6 = 0, then the single digit sum will be equal to 1.
- If N % 6 = 1, then the single digit sum will be equal to 2.
- If N % 6 = 2, then the single digit sum will be equal to 4.
- If N % 6 = 3, then the single digit sum will be equal to 8.
- If N % 6 = 4, then the single digit sum will be equal to 7.
- If N % 6 = 5, then the single digit sum will be equal to 5.
Follow the steps below to solve the problem:
- If N % 6 is 0 then print 1.
- Otherwise, if N % 6 is 1 then print 2.
- Otherwise, if N % 6 is 2 then print 7.
- Otherwise, if N % 6 is 3 then print 8.
- Otherwise, if N % 6 is 4 then print 7.
- Otherwise, if N % 6 is 5 then print 5.
Below is the implementation of the above approach:
C++
// 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 digitint findNumber(int N){ // Stores answers for // different values of N int ans[6] = { 1, 2, 4, 8, 7, 5 }; return ans[N % 6];}// Driver Codeint main(){ int N = 6; cout << findNumber(N) << endl; return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the number obtained// by reducing sum of digits of 2 ^ N// into a single digitstatic int findNumber(int N){ // Stores answers for // different values of N int []ans = {1, 2, 4, 8, 7, 5}; return ans[N % 6];}// Driver Codepublic static void main(String args[]){ int N = 6; System.out.println(findNumber(N));}}// This code is contributed by ipg2016107 |
Python3
# Python3 program for the above approach# Function to find the number obtained# by reducing sum of digits of 2 ^ N# into a single digitdef findNumber(N): # Stores answers for # different values of N ans = [ 1, 2, 4, 8, 7, 5 ] return ans[N % 6]# Driver Codeif __name__ == "__main__": N = 6 print (findNumber(N))# This code is contributed by ukasp |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the number obtained// by reducing sum of digits of 2 ^ N// into a single digitstatic int findNumber(int N){ // Stores answers for // different values of N int []ans = {1, 2, 4, 8, 7, 5}; return ans[N % 6];}// Driver Codepublic static void Main(){ int N = 6; Console.WriteLine(findNumber(N));}}// This code is contributed by mohit kumar 29 |
Javascript
<script>// JavaScript program for the above approach// Function to find the number obtained// by reducing sum of digits of 2 ^ N// into a single digitfunction 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
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
