Given an integer N, the task is to find the smallest positive integer, which when multiplied by N, has sum of digits equal to the sum of digits of N.
Examples:
Input: N = 4
Output: 28
Explanation:
- Sum of digits of N = 4
- 4 * 28 = 112
- Sum of digits = 1 + 1 + 2 = 4, which is equal to sum of digits of N.
Input: N = 3029
Output: 37
Explanation:
- Sum of digits of N = 3 + 0 + 2 + 9 = 14
- 3029 * 37 = 112073
- Sum of digits = 1 + 1 + 2 + 0 + 7 + 3 = 14, which is equal to sum of digits of N.
Approach: Follow the steps to solve the problem:
- Since N can be large, take the input of N as a string. Calculate the sum of digits of N and store it in a variable, say S.
- Since the answer needs to exceed 10, starting from number 11, multiply it with N and store it in a variable, say res.
- Calculate the sum of digits of res and check if the sum of digits of res is equal to the S or not. If found to be true, then print the integer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find the minimum// integer having sum of digits// of a number multiplied by n// equal to sum of digits of nvoid find_num(string n){ // Initialize answer int ans = 0; int sumOfDigitsN = 0; // Find sum of digits of N for(int c = 0; c < n.length(); c++) { sumOfDigitsN += n - '0'; } int x=11; while(true) { // Multiply N with x int newNum = x * stoi(n); int tempSumDigits = 0; string temp = to_string(newNum); // Sum of digits of the new number for(int c = 0; c < temp.length(); c++) { tempSumDigits += temp - '0'; } // If condition satisfies if (tempSumDigits == sumOfDigitsN) { ans = x; break; } //increase x x++; } // Print answer cout << ans << endl;}// Driver Codeint main() { string N = "3029"; // Function call find_num(N); return 0;}// This code is contributed by Sunil Sakariya |
Java
// Java program for the above approachclass GFG { // Function to find the minimum // integer having sum of digits // of a number multiplied by n // equal to sum of digits of n static void find_num(String n) { // Initialize answer int ans = 0; // Convert string to // character array char[] digitsOfN = n.toCharArray(); int sumOfDigitsN = 0; // Find sum of digits of N for (char c : digitsOfN) { sumOfDigitsN += Integer.parseInt( Character.toString(c)); } for (int x = 11; x > 0; x++) { // Multiply N with x int newNum = x * Integer.parseInt(n); int tempSumDigits = 0; char[] temp = Integer.toString( newNum) .toCharArray(); // Sum of digits of the new number for (char c : temp) { tempSumDigits += Integer.parseInt( Character.toString(c)); } // If condition satisfies if (tempSumDigits == sumOfDigitsN) { ans = x; break; } } // Print answer System.out.println(ans); } // Driver Code public static void main(String[] args) { String N = "3029"; // Function call find_num(N); }} |
Python3
# Python3 program for the above approach# Function to find the minimum# integer having sum of digits# of a number multiplied by n# equal to sum of digits of ndef find_num(n): # Initialize answer ans = 0 # Convert string to # character array digitsOfN = str(n) sumOfDigitsN = 0 # Find sum of digits of N for c in digitsOfN: sumOfDigitsN += int(c) for x in range(11, 50): # Multiply N with x newNum = x * int(n) tempSumDigits = 0 temp = str(newNum) # Sum of digits of the new number for c in temp: tempSumDigits += int(c) #print(tempSumDigits,newNum) # If condition satisfies if (tempSumDigits == sumOfDigitsN): ans = x break # Print answer print(ans)# Driver Codeif __name__ == '__main__': N = "3029" # Function call find_num(N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System;using System.Globalization; class GFG{ // Function to find the minimum// integer having sum of digits// of a number multiplied by n// equal to sum of digits of nstatic void find_num(string n){ // Initialize answer int ans = 0; // Convert string to // character array char[] digitsOfN = n.ToCharArray(); int sumOfDigitsN = 0; // Find sum of digits of N foreach(char c in digitsOfN) { sumOfDigitsN += Int32.Parse( Char.ToString(c)); } for(int x = 11; x > 0; x++) { // Multiply N with x int newNum = x * Int32.Parse(n); int tempSumDigits = 0; string str = newNum.ToString(); char[] temp = str.ToCharArray(); // Sum of digits of the new number foreach(char c in temp) { tempSumDigits += Int32.Parse( Char.ToString(c)); } // If condition satisfies if (tempSumDigits == sumOfDigitsN) { ans = x; break; } } // Print answer Console.WriteLine(ans);}// Driver Codepublic static void Main(){ string N = "3029"; // Function call find_num(N);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum// integer having sum of digits// of a number multiplied by n// equal to sum of digits of nfunction find_num(n){ // Initialize answer var ans = 0; var sumOfDigitsN = 0; // Find sum of digits of N for(var c = 0; c < n.length; c++) { sumOfDigitsN += n - '0'; } var x=11; while(true) { // Multiply N with x var newNum = x * parseInt(n); var tempSumDigits = 0; var temp = (newNum.toString()); // Sum of digits of the new number for(var c = 0; c < temp.length; c++) { tempSumDigits += temp - '0'; } // If condition satisfies if (tempSumDigits == sumOfDigitsN) { ans = x; break; } //increase x x++; } // Print answer document.write( ans );}// Driver Codevar N = "3029";// Function callfind_num(N);</script> |
Output:
37
Time Complexity: O(N)
Auxiliary Space: O(log N)
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!
