Check if a number is magic (Recursive sum of digits is 1)
A number is said to be a magic number, if the sum of its digits are calculated till a single digit recursively by adding the sum of the digits after every addition. If the single digit comes out to be 1,then the number is a magic number.
For example-
Number= 50113
=> 5+0+1+1+3=10
=> 1+0=1
This is a Magic Number
For example-
Number= 1234
=> 1+2+3+4=10
=> 1+0=1
This is a Magic Number
Examples :
Input : 1234 Output : Magic Number Input : 12345 Output : Not a magic Number
The approach used brute force. The function keeps adding digits until a single digit sum is reached. To understand how i am calculating the sum upto a single digit view this page- Finding sum of digits of a number until sum becomes single digit
C++
// CPP program to check if a number is Magic // number. #include<iostream> using namespace std; bool isMagic( int n) { int sum = 0; // Note that the loop continues // if n is 0 and sum is non-zero. // It stops when n becomes 0 and // sum becomes single digit. while (n > 0 || sum > 9) { if (n == 0) { n = sum; sum = 0; } sum += n % 10; n /= 10; } // Return true if sum becomes 1. return (sum == 1); } // Driver code int main() { int n = 1234; if (isMagic(n)) cout << "Magic Number" ; else cout << "Not a magic Number" ; return 0; } |
Java
// Java program to check if // a number is Magic number. import java.io.*; public class GFG { public static boolean isMagic( int n) { int sum = 0 ; // Note that the loop continues // if n is 0 and sum is non-zero. // It stops when n becomes 0 and // sum becomes single digit. while (n > 0 || sum > 9 ) { if (n == 0 ) { n = sum; sum = 0 ; } sum += n % 10 ; n /= 10 ; } // Return true if sum becomes 1. return (sum == 1 ); } // Driver code public static void main(String args[]) { int n = 1234 ; if (isMagic(n)) System.out.println( "Magic Number" ); else System.out.println( "Not a magic Number" ); } } // This code is contributed by Anshika Goyal. |
Python3
# Python3 program to check # if a number is Magic # number. def isMagic(n): sum = 0 ; # Note that the loop # continues if n is 0 # and sum is non-zero. # It stops when n becomes # 0 and sum becomes single # digit. while (n > 0 or sum > 9 ): if (n = = 0 ): n = sum ; sum = 0 ; sum = sum + n % 10 ; n = int (n / 10 ); # Return true if # sum becomes 1. return True if ( sum = = 1 ) else False ; # Driver code n = 1234 ; if (isMagic(n)): print ( "Magic Number" ); else : print ( "Not a magic Number" ); # This code is contributed # by mits. |
C#
// C# program to check if // a number is Magic number. using System; class GFG { public static bool isMagic( int n) { int sum = 0; // Note that the loop continues // if n is 0 and sum is non-zero. // It stops when n becomes 0 and // sum becomes single digit. while (n > 0 || sum > 9) { if (n == 0) { n = sum; sum = 0; } sum += n % 10; n /= 10; } // Return true if sum becomes 1. return (sum == 1); } // Driver code public static void Main() { int n = 1234; if (isMagic(n)) Console.WriteLine( "Magic Number" ); else Console.WriteLine( "Not a magic Number" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to check if // a number is Magic number. function isMagic( $n ) { $sum = 0; // Note that the loop // continues if n is 0 // and sum is non-zero. // It stops when n becomes // 0 and sum becomes single // digit. while ( $n > 0 || $sum > 9) { if ( $n == 0) { $n = $sum ; $sum = 0; } $sum += $n % 10; $n /= 10; } // Return true if // sum becomes 1. return ( $sum == 1); } // Driver code $n = 1234; if (isMagic( $n )) echo "Magic Number" ; else echo "Not a magic Number" ; // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // JavaScript program to check if // a number is Magic number. function isMagic( n) { var sum = 0; // Note that the loop continues // if n is 0 and sum is non-zero. // It stops when n becomes 0 and // sum becomes single digit. while (n > 0 || sum > 9) { if (n = 0) { n = sum; sum = 0; } sum += n % 10; n /= 10; } // Return true if sum becomes 1. return (sum = 1); } // Driver code var n = 1234; if (isMagic(n)) document.write( "Magic Number" ); else document.write( "Not a magic Number" ); // This code is contributed by shivanisinghss2110 </script> |
Magic Number
Time Complexity: O(log10n)
Auxiliary Space: O(1), As constant extra space is used.
Efficient Approach(Shortcut): There is also a shortcut method to verify Magic Number. The function will determine if the remainder on dividing the input by 9 is 1 or not. If it is 1, then the number is a magic number. The divisibility rule of 9 says that a number is divisible by 9 if the sum of its digits are also divisible by 9. Therefore, if a number is divisible by 9, then, recursively, all the digit sums are also divisible by 9. The final digit sum is always 9. An increase of 1 in the original number will increase the ultimate value by 1, making it 10 and the ultimate sum will be 1, thus verifying that it is a magic number.
C++
// C++ program to check // Whether the number is Magic or not. #include <iostream> using namespace std; int main() { // Accepting sample input int x = 1234; // Condition to check Magic number if (x%9==1) cout << ( "Magic Number" ); else cout << ( "Not a Magic Number" ); return 0; } |
C
// C program to check // Whether the number is Magic or not. #include <stdio.h> int main() { // Accepting sample input int x = 1234; // Condition to check Magic number if (x%9==1) printf ( "Magic Number" ); else printf ( "Not a Magic Number" ); return 0; } |
Java
// Java program to check // Whether the number is Magic or not. import java.io.*; public class GFG{ public static void main(String[] args) { // Accepting sample input int x = 1234 ; // Condition to check Magic number if (x % 9 == 1 ) System.out.printf( "Magic Number" ); else System.out.printf( "Not a Magic Number" ); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to check # Whether the number is Magic or not. # Accepting sample input x = 1234 # Condition to check Magic number if (x % 9 = = 1 ): print ( "Magic Number" ) else : print ( "Not a Magic Number" ) # This code is contributed by kirti |
C#
// C# program to check // Whether the number is Magic or not. using System; using System.Collections.Generic; class GFG{ public static void Main(String[] args) { // Accepting sample input int x = 1234; // Condition to check Magic number if (x % 9 == 1) Console.Write( "Magic Number" ); else Console.Write( "Not a Magic Number" ); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to check // Whether the number is Magic or not. // Accepting sample input var x = 1234; // Condition to check Magic number if (x % 9 == 1) document.write( "Magic Number" ); else document.write( "Not a Magic Number" ); // This code is contributed by shivanisinghss2110 </script> |
Magic Number
Time Complexity: O(1)
Auxiliary Space: O(1) As constant extra space is used.