Given an integer N, the task is to print the first N terms whose sum of digits is a multiple of 10. First few terms of the series are 19, 28, 37, 46, 55, …
Examples:
Input: N = 5
Output: 19 28 37 46 55
Input: N = 10
Output: 19 28 37 46 55 64 73 82 91 109
Approach: It can be observed that to get the Nth term of the required series, find the sum of the digits of N. If the sum is already a multiple of 10 then append digit 0 in the end of N else append the minimum possible digit in the end such that the new sum of digits is a multiple of 10.
For example, to get the 19th term, since the sum of digits is already a multiple of 10 then append 0 and 190 is the 19th term of the series.
For N = 5, the minimum digit that can be appended to make the sum of digits as a multiple of 10 is 5 and 55 is the 5th term of the series.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;const int TEN = 10;// Function to return the// sum of digits of nint digitSum(int n){ int sum = 0; while (n > 0) { // Add last digit to the sum sum += n % TEN; // Remove last digit n /= TEN; } return sum;}// Function to return the nth term// of the required seriesint getNthTerm(int n){ int sum = digitSum(n); // If sum of digit is already // a multiple of 10 then append 0 if (sum % TEN == 0) return (n * TEN); // To store the minimum digit // that must be appended int extra = TEN - (sum % TEN); // Return n after appending // the required digit return ((n * TEN) + extra);}// Function to print the first n terms// of the required seriesvoid firstNTerms(int n){ for (int i = 1; i <= n; i++) cout << getNthTerm(i) << " ";}// Driver codeint main(){ int n = 10; firstNTerms(n); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG { final static int TEN = 10; // Function to return the // sum of digits of n static int digitSum(int n) { int sum = 0; while (n > 0) { // Add last digit to the sum sum += n % TEN; // Remove last digit n /= TEN; } return sum; } // Function to return the nth term // of the required series static int getNthTerm(int n) { int sum = digitSum(n); // If sum of digit is already // a multiple of 10 then append 0 if (sum % TEN == 0) return (n * TEN); // To store the minimum digit // that must be appended int extra = TEN - (sum % TEN); // Return n after appending // the required digit return ((n * TEN) + extra); } // Function to print the first n terms // of the required series static void firstNTerms(int n) { for (int i = 1; i <= n; i++) System.out.print(getNthTerm(i) + " "); } // Driver code public static void main (String[] args) { int n = 10; firstNTerms(n); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 code for above implementationTEN = 10# Function to return the# sum of digits of ndef digitSum(n): sum = 0 while (n > 0): # Add last digit to the sum sum += n % TEN # Remove last digit n //= TEN return sum# Function to return the nth term# of the required seriesdef getNthTerm(n): sum = digitSum(n) # If sum of digit is already # a multiple of 10 then append 0 if (sum % TEN == 0): return (n * TEN) # To store the minimum digit # that must be appended extra = TEN - (sum % TEN) # Return n after appending # the required digit return ((n * TEN) + extra)# Function to print the first n terms# of the required seriesdef firstNTerms(n): for i in range(1, n + 1): print(getNthTerm(i), end = " ")# Driver coden = 10firstNTerms(n)# This code is contributed by Mohit Kumar |
C#
// C# Program to Find the Unique elements // in linked listsusing System; class GFG { readonly static int TEN = 10; // Function to return the // sum of digits of n static int digitSum(int n) { int sum = 0; while (n > 0) { // Add last digit to the sum sum += n % TEN; // Remove last digit n /= TEN; } return sum; } // Function to return the nth term // of the required series static int getNthTerm(int n) { int sum = digitSum(n); // If sum of digit is already // a multiple of 10 then append 0 if (sum % TEN == 0) return (n * TEN); // To store the minimum digit // that must be appended int extra = TEN - (sum % TEN); // Return n after appending // the required digit return ((n * TEN) + extra); } // Function to print the first n terms // of the required series static void firstNTerms(int n) { for (int i = 1; i <= n; i++) Console.Write(getNthTerm(i) + " "); } // Driver code public static void Main (String[] args) { int n = 10; firstNTerms(n); } }// This code is contributed by 29AjayKumar |
Javascript
const TEN = 10;// Function to return the// sum of digits of nfunction digitSum(n){ let sum = 0; while (n > 0) { // Add last digit to the sum sum += n % TEN; // Remove last digit n = Math.floor(n / TEN); } return sum;}// Function to return the nth term// of the required seriesfunction getNthTerm(n){ let sum = digitSum(n); // If sum of digit is already // a multiple of 10 then append 0 if (sum % TEN == 0) return (n * TEN); // To store the minimum digit // that must be appended let extra = TEN - (sum % TEN); // Return n after appending // the required digit return ((n * TEN) + extra);}// Function to print the first n terms// of the required seriesfunction firstNTerms(n){ for (let i = 1; i <= n; i++) console.log(getNthTerm(i) + " ");}// Driver code let n = 10; firstNTerms(n);// This code is contributed by Surbhi Tyagi. |
19 28 37 46 55 64 73 82 91 109
New Approach:- Another approach to solve this problem is to generate the series by iterating over all numbers from 1 to infinity and selecting only those numbers whose sum of digits is a multiple of 10.
Algorithm :-
- Define a function named digitSum that takes an integer n as input and returns the sum of its digits.
- Define a function named firstNTerms that takes an integer n as input and prints the first n terms of the required series.
- Inside the firstNTerms function, initialize a variable count to 0.
- Use a for loop to iterate over all integers from 1 to infinity until n terms whose sum of digits is a multiple of 10 are found.
- Inside the loop, call the digitSum function for the current integer I.
- If the sum of digits of i is a multiple of 10, print i and increment the count variable.
- If count reaches n, exit the loop and return.
- In the main function, call the firstNTerms function with the value of n to print the first n terms of the required series.
Here’s the implementation of this approach:
C++
#include <bits/stdc++.h>using namespace std; // Function to return the sum of digits of n intdigitSum (int n) { int sum = 0; while (n > 0) { // Add last digit to the sum sum += n % 10; // Remove last digit n /= 10; } return sum;} // Function to print the first n terms of the required series voidfirstNTerms (int n) { int count = 0; for (int i = 1; count < n; i++) { if (digitSum (i) % 10 == 0) { cout << i << " "; count++; } }} // Driver code intmain () { int n = 10; firstNTerms (n); return 0;} |
Java
import java.util.*;public class Main { // Function to return the sum of digits of n public static int digitSum(int n) { int sum = 0; while (n > 0) { // Add last digit to the sum sum += n % 10; // Remove last digit n /= 10; } return sum; } // Function to print the first n terms of the required // series public static void firstNTerms(int n) { int count = 0; for (int i = 1; count < n; i++) { if (digitSum(i) % 10 == 0) { System.out.print(i + " "); count++; } } } // Driver code public static void main(String[] args) { int n = 10; firstNTerms(n); }} |
Python3
def digitSum(n): sum = 0 while n > 0: # Add last digit to the sum sum += n % 10 # Remove last digit n //= 10 return sumdef firstNTerms(n): count = 0 i = 1 while count < n: if digitSum(i) % 10 == 0: print(i, end=" ") count += 1 i += 1n = 10firstNTerms(n) |
C#
// C# program for the above approachusing System;public class GFG{ // Function to return the sum of digits of n public static int DigitSum(int n) { int sum = 0; while (n > 0) { // Add the last digit to the sum sum += n % 10; // Remove last digit n /= 10; } return sum; } // Function to print the first n terms of the required series public static void FirstNTerms(int n) { int count = 0; for (int i = 1; count < n; i++) { if (DigitSum(i) % 10 == 0) { Console.Write(i + " "); count++; } } } // Driver Code public static void Main(string[] args) { int n = 10; FirstNTerms(n); }} |
Javascript
// Function to return the sum of digits of nfunction digitSum(n) { let sum = 0; while (n > 0) { // Add the last digit to the sum sum += n % 10; // Remove the last digit n = Math.floor(n / 10); } return sum;}// Function to print the first n terms of the required seriesfunction firstNTerms(n) { let count = 0; for (let i = 1; count < n; i++) { if (digitSum(i) % 10 === 0) { console.log(i + " "); count++; } }}// Driver Codeconst n = 10;firstNTerms(n); |
19 28 37 46 55 64 73 82 91 109
“In this approach, we first define a function digitSum to calculate the sum of digits of a given number. Then, we iterate over all numbers from 1 to infinity and check if the sum of digits of each number is a multiple of 10. If it is, we print that number and increment the count of printed terms until we reach the desired number of terms.”
Time complexity:
The digitSum function runs in O(log10(n)) time complexity as it iterates over the digits of the number and removes one digit in each iteration.
The firstNTerms function iterates over all numbers from 1 to infinity until it finds n terms whose sum of digits is a multiple of 10. In the worst case, it may need to iterate over all integers up to 10n to find n terms, as every tenth integer has a sum of digits that is a multiple of 10. Therefore, the time complexity of this function is O(n log n).
Space complexity:
The digitSum function uses a constant amount of extra memory to store the sum variable. The firstNTerms function uses a constant amount of extra memory to store the count variable. Therefore, the space complexity of both functions is O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
