Sum of all armstrong numbers lying in the range [L, R] for Q queries
Given Q queries in the form of a 2D array arr[][] in which every row consists of two numbers L and R which denotes a range [L, R], the task is to find the sum of all Armstrong Numbers lying in the given range [L, R].
Examples:
Input: Q = 2, arr = [ [1, 13], [121, 211] ]
Output:
45
153
Explanation:
From 1 to 13, 1, 2, 3, 4, 5, 6, 7, 8 and 9 are the Armstrong number. Therefore the sum is 45.
From 121 to 211 there is only one Armstrong number i.e., 153. So the sum is 153.
Input: Q = 4, arr = [ [ 10, 10 ], [ 258, 785 ], [45, 245], [ 1, 1000]]
Output:
0
1148
153
1346
Approach:
The idea is to use a Prefix Sum Array. The sum of all Armstrong Number till that particular index is precomputed and stored in an array pref[] so that every query can be answered in O(1) time.
- Initialise the prefix array pref[].
- Iterate from 1 to N and check if the number is Armstrong or not:
- If the number is Armstrong then, the current index of pref[] will store the count of Armstrong Numbers found so far calculated by (1 + the number at previous index of pref[]).
- Else the current index of pref[] is same as the value at previous index of pref[].
- For Q queries the sum of all Armstrong Numbers for range [L, R] can be calculated as follows:
sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach
C++
// C++ program to find the sum // of all armstrong numbers // in the given range #include <bits/stdc++.h> using namespace std; // pref[] array to precompute // the sum of all armstrong // number int pref[100001] = {0}; // Function that return number // num if num is armstrong // else return 0 static int checkArmstrong( int x) { int n = to_string(x).size(); int sum1 = 0; int temp = x; while (temp > 0) { int digit = temp % 10; sum1 += pow (digit, n); temp /= 10; } if (sum1 == x) return x; return 0; } // Function to precompute the // sum of all armstrong numbers // upto 100000 void preCompute() { for ( int i = 1; i < 100001; i++) { // checkarmstrong () // return the number i // if i is armstrong // else return 0 pref[i] = pref[i - 1] + checkArmstrong(i); } } // Function to print the sum // for each query void printSum( int L, int R) { cout<<(pref[R] - pref[L - 1])<<endl; } // Function to print sum of all // armstrong numbers between // [L, R] void printSumarmstrong( int arr[2][2], int Q) { // Function that pre computes // the sum of all armstrong // numbers preCompute(); // Iterate over all Queries // to print the sum for ( int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } int main() { // Queries int Q = 2; int arr[2][2] = { { 1, 13 }, { 121, 211 } }; // Function that print the // the sum of all armstrong // number in Range [L, R] printSumarmstrong(arr, Q); return 0; } // This code is contributed by 29AjayKumar |
Java
// Java program to find the sum // of all armstrong numbers // in the given range class GFG { // pref[] array to precompute // the sum of all armstrong // number static int [] pref = new int [ 100001 ]; // Function that return number // num if num is armstrong // else return 0 static int checkArmstrong( int x) { int n = String.valueOf(x).length(); int sum1 = 0 ; int temp = x; while (temp > 0 ) { int digit = temp % 10 ; sum1 += Math.pow(digit, n); temp /= 10 ; } if (sum1 == x) return x; return 0 ; } // Function to precompute the // sum of all armstrong numbers // upto 100000 static void preCompute() { for ( int i = 1 ; i < 100001 ; i++) { // checkarmstrong () // return the number i // if i is armstrong // else return 0 pref[i] = pref[i - 1 ] + checkArmstrong(i); } } // Function to print the sum // for each query static void printSum( int L, int R) { System.out.println(pref[R] - pref[L - 1 ]); } // Function to print sum of all // armstrong numbers between // [L, R] static void printSumarmstrong( int [][] arr, int Q) { // Function that pre computes // the sum of all armstrong // numbers preCompute(); // Iterate over all Queries // to print the sum for ( int i = 0 ; i < Q; i++) { printSum(arr[i][ 0 ], arr[i][ 1 ]); } } // Driver code public static void main(String[] args) { // Queries int Q = 2 ; int [][] arr = { { 1 , 13 }, { 121 , 211 } }; // Function that print the // the sum of all armstrong // number in Range [L, R] printSumarmstrong(arr, Q); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the sum # of all armstrong numbers # in the given range # pref[] array to precompute # the sum of all armstrong # number pref = [ 0 ] * 100001 # Function that return number # num if num is armstrong # else return 0 def checkArmstrong(x): n = len ( str (x)) sum1 = 0 temp = x while temp > 0 : digit = temp % 10 sum1 + = digit * * n temp / / = 10 if sum1 = = x: return x return 0 # Function to precompute the # sum of all armstrong numbers # upto 100000 def preCompute(): for i in range ( 1 , 100001 ): # checkarmstrong () # return the number i # if i is armstrong # else return 0 pref[i] = pref[i - 1 ] + checkArmstrong(i) # Function to print the sum # for each query def printSum(L, R): print (pref[R] - pref[L - 1 ]) # Function to print sum of all # armstrong numbers between # [L, R] def printSumarmstrong (arr, Q): # Function that pre computes # the sum of all armstrong # numbers preCompute() # Iterate over all Queries # to print the sum for i in range (Q): printSum(arr[i][ 0 ], arr[i][ 1 ]) # Driver code # Queries Q = 2 arr = [[ 1 , 13 ], [ 121 , 211 ]] # Function that print the # the sum of all armstrong # number in Range [L, R] printSumarmstrong (arr, Q) |
C#
// C# program to find the sum // of all armstrong numbers // in the given range using System; class GFG { // pref[] array to precompute // the sum of all armstrong // number static int [] pref = new int [100001]; // Function that return number // num if num is armstrong // else return 0 static int checkArmstrong( int x) { int n = x.ToString().Length; int sum1 = 0; int temp = x; while (temp > 0) { int digit = temp % 10; sum1 += ( int )Math.Pow(digit, n); temp /= 10; } if (sum1 == x) return x; return 0; } // Function to precompute the // sum of all armstrong numbers // upto 100000 static void preCompute() { for ( int i = 1; i < 100001; i++) { // checkarmstrong () // return the number i // if i is armstrong // else return 0 pref[i] = pref[i - 1] + checkArmstrong(i); } } // Function to print the sum // for each query static void printSum( int L, int R) { Console.WriteLine(pref[R] - pref[L - 1]); } // Function to print sum of all // armstrong numbers between // [L, R] static void printSumarmstrong( int [,] arr, int Q) { // Function that pre computes // the sum of all armstrong // numbers preCompute(); // Iterate over all Queries // to print the sum for ( int i = 0; i < Q; i++) { printSum(arr[i, 0], arr[i, 1]); } } // Driver code public static void Main( string [] args) { // Queries int Q = 2; int [,] arr = { { 1, 13 }, { 121, 211 } }; // Function that print the // the sum of all armstrong // number in Range [L, R] printSumarmstrong(arr, Q); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript program to find the sum // of all armstrong numbers // in the given range // pref[] array to precompute // the sum of all armstrong // number let pref = new Array(100001); pref.fill(0); // Function that return number // num if num is armstrong // else return 0 function checkArmstrong(x) { let n = (x.toString()).length; let sum1 = 0; let temp = x; while (temp > 0) { let digit = temp % 10; sum1 += Math.pow(digit, n); temp = parseInt(temp / 10, 10); } if (sum1 == x) return x; return 0; } // Function to precompute the // sum of all armstrong numbers // upto 100000 function preCompute() { for (let i = 1; i < 100001; i++) { // checkarmstrong () // return the number i // if i is armstrong // else return 0 pref[i] = pref[i - 1] + checkArmstrong(i); } } // Function to print the sum // for each query function printSum(L, R) { document.write((pref[R] - pref[L - 1]) + "</br>" ); } // Function to print sum of all // armstrong numbers between // [L, R] function printSumarmstrong(arr, Q) { // Function that pre computes // the sum of all armstrong // numbers preCompute(); // Iterate over all Queries // to print the sum for (let i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } // Queries let Q = 2; let arr = [ [ 1, 13 ], [ 121, 211 ] ]; // Function that print the // the sum of all armstrong // number in Range [L, R] printSumarmstrong(arr, Q); // This code is contributed by divyesh072019. </script> |
Output:
45 153
Time Complexity: O(N), where N is the maximum element in the query.
Auxiliary Space: O(105)