Tutorialspoint.dev

GCD of digits of a given number

Given a number n, find GCD of its digits.

Examples :

Input  : 345
Output : 1
GCD of 3, 4 and 5 is 1.

Input  : 2448
Output : 2
GCD of 2, 4, 4 and 8 is 2



We traverse the digits of number one by one using below loop

digit = n mod 10;
n  = n / 10; 

While traversing digits, we keep track of current GCD and keep updating GCD by finding GCD of current digit with current GCD.

C++

// CPP program to find GCD of digits of a number
#include<iostream>
#include<algorithm>
using namespace std;
  
int digitGCD(int n)
{
    int gcd = 0;
    while (n > 0)
    {        
        gcd = __gcd(n%10, gcd);
  
        // If at point GCD becomes 1,
        // return it
        if (gcd == 1)
           return 1;
  
        n = n/10;
    }
    return gcd;
}
  
// driver code
int main()
{
    long n = 2448;
    cout << digitGCD(n);
    return 0;
}

Java

// Java program to find GCD of digits of a number
  
class GFG
{
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    
        return b == 0 ? a : __gcd(b, a % b); 
          
    }
    static int digitGCD(int n)
    {
        int gcd = 0;
        while (n > 0)
        {     
            gcd = __gcd(n % 10, gcd);
      
            // If at point GCD becomes 1,
            // return it
            if (gcd == 1)
            return 1;
      
            n = n / 10;
        }
        return gcd;
    }
      
    // Driver code
    public static void main (String[] args) 
    {
        int n = 2448;
        System.out.print(digitGCD(n));
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python program to find 
# GCD of digits of a number
  
# Recursive function to return gcd of a and b
def __gcd(a,b):
    return a if(b==0) else __gcd(b, a % b)
      
def digitGCD(n):
  
    gcd = 0
    while (n > 0):
      
        gcd = __gcd(n % 10, gcd)
   
        # If at point GCD becomes 1,
        # return it
        if (gcd == 1):
           return 1
   
        n = n // 10
      
    return gcd
  
#Driver code
n = 2448
print(digitGCD(n))
  
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find GCD of
// digits of a number
using System;
  
class GFG {
      
    // Recursive function to return 
    // gcd of a and b
    static int __gcd(int a, int b)
    
        return b == 0 ? a : __gcd(b, a % b); 
          
    }
      
    static int digitGCD(int n)
    {
        int gcd = 0;
        while (n > 0)
        {     
            gcd = __gcd(n % 10, gcd);
      
            // If at point GCD becomes 1,
            // return it
            if (gcd == 1)
            return 1;
      
            n = n / 10;
        }
        return gcd;
    }
      
    // Driver code
    public static void Main () 
    {
        int n = 2448;
        Console.Write(digitGCD(n));
    }
}
  
// This code is contributed by Nitin Mittal.

PHP

<?php
// PHP program to find GCD 
// of digits of a number
  
// Recursive function to 
// return gcd of a and b
function __gcd($a,$b)
    return $b == 0 ? $a
      __gcd($b, $a % $b); 
          
}
      
function digitGCD($n)
{
    $gcd = 0;
    while ($n > 0)
    {     
        $gcd = __gcd($n % 10, $gcd);
  
        // If at point GCD 
        // becomes 1, return it
        if ($gcd == 1)
        return 1;
  
        $n = $n / 10;
    }
    return $gcd;
}
  
// Driver code
$n = 2448;
echo digitGCD($n);
  
// This code is contributed by Sam007
?>


Output :

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter