Given a range of positive integers, find the Greatest Common Divisor (GCD) of the largest and smallest Armstrong numbers within that range.
Examples:
Input: Range [100, 10000]
Output: 3
Explanation: Smallest Armstrong number in the given range is 153, and the largest Armstrong number in the given range is 9474. The GCD of 153 and 9474 is 3.Input: Range [200, 20000]
Output: 2
Explanation: Smallest Armstrong number in the given range is 370, and the largest Armstrong number in the given range is 9474. The GCD of 370 and 9474 is 2.
Approach: This can be solved with the following idea:
- Iterate through the given range of positive integers.
- For each number, check if it is an Armstrong number.
- If it is, update the smallest and largest Armstrong numbers found so far.
- Once the iteration is complete, find the GCD of the smallest and largest Armstrong numbers using a standard GCD algorithm.
Below are the steps to implement the above idea:
- Initialize variables to keep track of the smallest and largest Armstrong numbers found so far and set them to the minimum and maximum possible integer values respectively.
- Iterate through the given range of positive integers.
- For each number, calculate the sum of its digits raised to the power of the number of digits and check if it is equal to the original number. If it is, update the smallest and largest Armstrong numbers found so far.
- Once the iteration is complete, find the GCD of the smallest and largest Armstrong numbers using a standard GCD algorithm.
- Print the GCD as the final output.
Below is the code for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to check if a number is an// Armstrong numberbool isArmstrong(int num){ int originalNum = num; int sum = 0; int numDigits = to_string(num).length(); while (num > 0) { int digit = num % 10; sum += pow(digit, numDigits); num /= 10; } return sum == originalNum;}// Function to find the GCD of two numbersint gcd(int a, int b){ if (b == 0) { return a; } return gcd(b, a % b);}// Find GCDvoid gcdProduct(int rangeStart, int rangeEnd){ int smallestArmstrong = INT_MAX; int largestArmstrong = INT_MIN; // Iterate through the given range for (int i = rangeStart; i <= rangeEnd; i++) { if (isArmstrong(i)) { smallestArmstrong = min(smallestArmstrong, i); largestArmstrong = max(largestArmstrong, i); } } if (smallestArmstrong == INT_MAX || largestArmstrong == INT_MIN) { cout << endl; } else { int gcdResult = gcd(smallestArmstrong, largestArmstrong); cout << gcdResult << endl; }}// Driver codeint main(){ int rangeStart = 100; int rangeEnd = 10000; // Function call gcdProduct(rangeStart, rangeEnd); return 0;} |
Java
// JAVA code for the above approach:import java.util.*;public class GCDOfArmstrongNumbers { // Function to check if a number is an Armstrong number public static boolean isArmstrong(int num) { int originalNum = num; int sum = 0; int numDigits = String.valueOf(num).length(); while (num > 0) { int digit = num % 10; sum += Math.pow(digit, numDigits); num /= 10; } return sum == originalNum; } // Function to find the GCD of two numbers public static int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } // Find GCD public static void gcdProduct(int rangeStart, int rangeEnd) { int smallestArmstrong = Integer.MAX_VALUE; int largestArmstrong = Integer.MIN_VALUE; // Iterate through the given range for (int i = rangeStart; i <= rangeEnd; i++) { if (isArmstrong(i)) { smallestArmstrong = Math.min(smallestArmstrong, i); largestArmstrong = Math.max(largestArmstrong, i); } } if (smallestArmstrong == Integer.MAX_VALUE || largestArmstrong == Integer.MIN_VALUE) { System.out.println(); } else { int gcdResult = gcd(smallestArmstrong, largestArmstrong); System.out.println(gcdResult); } } // Driver code public static void main(String[] args) { int rangeStart = 100; int rangeEnd = 10000; // Function call gcdProduct(rangeStart, rangeEnd); }}// This code is contributed by shivamgupta098765421 |
Python3
# Python3 code for the above approach:import math# Function to check if a number is an Armstrong numberdef isArmstrong(num): originalNum = num sum = 0 numDigits = len(str(num)) while num > 0: digit = num % 10 sum += math.pow(digit, numDigits) num //= 10 return sum == originalNum# Function to find the GCD of two numbersdef gcd(a, b): if b == 0: return a return gcd(b, a % b)# Find GCDdef gcdProduct(rangeStart, rangeEnd): smallestArmstrong = float('inf') largestArmstrong = float('-inf') # Iterate through the given range for i in range(rangeStart, rangeEnd + 1): if isArmstrong(i): smallestArmstrong = min(smallestArmstrong, i) largestArmstrong = max(largestArmstrong, i) if smallestArmstrong == float('inf') or largestArmstrong == float('-inf'): print() else: gcdResult = gcd(smallestArmstrong, largestArmstrong) print(gcdResult)# Driver codeif __name__ == '__main__': rangeStart = 100 rangeEnd = 10000 # Function call gcdProduct(rangeStart, rangeEnd)# This code is contribued by rambabuguphka |
C#
using System;class GFG { // Function to check if a number is an Armstrong number static bool IsArmstrong(int num) { int originalNum = num; int sum = 0; int numDigits = num.ToString().Length; while (num > 0) { int digit = num % 10; sum += (int)Math.Pow(digit, numDigits); num /= 10; } return sum == originalNum; } // Function to find the GCD of two numbers static int Gcd(int a, int b) { if (b == 0) { return a; } return Gcd(b, a % b); } // Find GCD static void GcdProduct(int rangeStart, int rangeEnd) { int smallestArmstrong = int.MaxValue; int largestArmstrong = int.MinValue; // Iterate through the given range for (int i = rangeStart; i <= rangeEnd; i++) { if (IsArmstrong(i)) { smallestArmstrong = Math.Min(smallestArmstrong, i); largestArmstrong = Math.Max(largestArmstrong, i); } } if (smallestArmstrong == int.MaxValue || largestArmstrong == int.MinValue) { Console.WriteLine(); } else { int gcdResult = Gcd(smallestArmstrong, largestArmstrong); Console.WriteLine(gcdResult); } } // Driver code static void Main() { int rangeStart = 100; int rangeEnd = 10000; // Function call GcdProduct(rangeStart, rangeEnd); }} |
Javascript
// Function to check if a number is an Armstrong numberfunction isArmstrong(num) { const originalNum = num; let sum = 0; const numDigits = String(num).length; while (num > 0) { const digit = num % 10; sum += Math.pow(digit, numDigits); num = Math.floor(num / 10); } return sum === originalNum;}// Function to find the GCD of two numbersfunction gcd(a, b) { if (b === 0) { return a; } return gcd(b, a % b);}// Find GCDfunction gcdProduct(rangeStart, rangeEnd) { let smallestArmstrong = Number.MAX_SAFE_INTEGER; let largestArmstrong = Number.MIN_SAFE_INTEGER; // Iterate through the given range for (let i = rangeStart; i <= rangeEnd; i++) { if (isArmstrong(i)) { smallestArmstrong = Math.min(smallestArmstrong, i); largestArmstrong = Math.max(largestArmstrong, i); } } if (smallestArmstrong === Number.MAX_SAFE_INTEGER || largestArmstrong === Number.MIN_SAFE_INTEGER) { console.log(); } else { const gcdResult = gcd(smallestArmstrong, largestArmstrong); console.log(gcdResult); }}// Driver codeconst rangeStart = 100;const rangeEnd = 10000;// Function callgcdProduct(rangeStart, rangeEnd);// This code is contributed by shivamgupta310570 |
Output
3
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
