Given a number n and a number d, we can add d to n as many times ( even 0 is possible ). The task is to find the minimum possible digit sum we can achieve by performing above operation.
Digit Sum is defined as the sum of digits of a number recursively until it is less than 10.
Examples:
Input: n = 2546, d = 124 Output: 1 2546 + 8*124 = 3538 DigitSum(3538)=1 Input: n = 123, d = 3 Output: 3
Approach:
- First observation here is to use %9 approach to find minimum possible digit sum of a number n. If modulo with 9 is 0 return 9 else return the remainder.
- Second observation is, a+d*(9k+l) modulo 9 is equivalent to a+d*l modulo 9, therefore, the answer to the query will be available in either no addition or first 8 additions of d, after which the digit sum will repeat.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function To find digitsum for a numberint digitsum(int n){ // Logic for digitsum int r = n % 9; if (r == 0) return 9; else return r;}// Function to find minimum digit sumint find(int n, int d){ // Variable to store answer // Initialise by 10 as the answer // will always be less than 10 int minimum = 10; // Values of digitsum will repeat after // i=8, due to modulo taken with 9 for (int i = 0; i < 9; i++) { int current = (n + i * d); minimum = min(minimum, digitsum(current)); } return minimum;}// Driver Codeint main(){ int n = 2546, d = 124; cout << "Minimum possible digitsum is :" << find(n, d); return 0;} |
Java
// Java implementation of above approachimport java.io.*;public class gfg{ // Function To find digitsum for a numberpublic int digitsum(int n){ // Logic for digitsum int r = n % 9; if (r == 0) return 9; else return r;}// Function to find minimum digit sumpublic int find(int n, int d){ // Variable to store answer // Initialise by 10 as the answer // will always be less than 10 int minimum = 10; // Values of digitsum will repeat after // i=8, due to modulo taken with 9 for (int i = 0; i < 9; i++) { int current = (n + i * d); minimum = Math.min(minimum, digitsum(current)); } return minimum;}}class geek{// Driver Codepublic static void main(String[]args){ gfg g = new gfg(); int n = 2546, d = 124; System.out.println("Minimum possible digitsum is : "+ (g.find(n, d)));}}//This code is contributed by shs.. |
Python3
# Python3 implementation of # above approach# Function To find digitsum # for a numberdef digitsum(n): # Logic for digitsum r = n % 9; if (r == 0): return 9; else: return r;# Function to find minimum digit sumdef find(n, d): # Variable to store answer # Initialise by 10 as the answer # will always be less than 10 minimum = 10; # Values of digitsum will # repeat after i=8, due to # modulo taken with 9 for i in range(9): current = (n + i * d); minimum = min(minimum, digitsum(current)); return minimum;# Driver Coden = 2546; d = 124;print("Minimum possible digitsum is :", find(n, d));# This code is contributed by mits |
C#
// C# implementation of above approachusing System;public class gfg{ // Function To find digitsum for a number public int digitsum(int n) { // Logic for digitsum int r = n % 9; if (r == 0) return 9; else return r; }// Function to find minimum digit sum public int find(int n, int d) { // Variable to store answer // Initialise by 10 as the answer // will always be less than 10 int minimum = 10; // Values of digitsum will repeat after // i=8, due to modulo taken with 9 for (int i = 0; i < 9; i++) { int current = (n + i * d); minimum = Math.Min(minimum, digitsum(current)); } return minimum; }}class geek{// Driver Code public static void Main() { gfg g = new gfg(); int n = 2546, d = 124; Console.WriteLine("Minimum possible digitsum is : {0}", (g.find(n, d))); Console.Read(); }}//This code is contributed by SoumikMondal |
PHP
<?php// PHP implementation of // above approach// Function To find digitsum // for a numberfunction digitsum($n){ // Logic for digitsum $r = $n % 9; if ($r == 0) return 9; else return $r;}// Function to find minimum digit sumfunction find($n, $d){ // Variable to store answer // Initialise by 10 as the answer // will always be less than 10 $minimum = 10; // Values of digitsum will // repeat after i=8, due to // modulo taken with 9 for ($i = 0; $i < 9; $i++) { $current = ($n + $i * $d); $minimum = min($minimum, digitsum($current)); } return $minimum;}// Driver Code$n = 2546; $d = 124;echo "Minimum possible digitsum is :", find($n, $d);// This code is contributed // by Shashank?> |
Javascript
<script>// javascript implementation of above approach // Function To find digitsum for a number function digitsum( n) { // Logic for digitsum var r = n % 9; if (r == 0) return 9; else return r; } // Function to find minimum digit sum function find( n, d) { // Variable to store answer // Initialise by 10 as the answer // will always be less than 10 var minimum = 10; // Values of digitsum will repeat after // i=8, due to modulo taken with 9 for (var i = 0; i < 9; i++) { var current = (n + i * d); minimum = Math.min(minimum, digitsum(current)); } return minimum; } var n = 2546, d = 124; document.write("Minimum possible digitsum is :" + find(n, d)); </script> |
Output:
Minimum possible digitsum is :1
Time Complexity: O(9)
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!
