Given two integers N and X, the task is to find the minimum count of integers with sum N and having unit digit X. If no such representation exists then print -1.
Examples:
Input: N = 38, X = 9
Output: 2
Explanation:
Minimum two integers are required with unit digit as X to represent as a sum equal to 38.
38 = 19 + 19 or 38 = 29 + 9
Input: N = 6, X = 4
Output: -1
Explanation:
No such representation of
Approach:
Follow the steps below to solve the problem:
- Obtain the unit digit of N and check if it achieved by the sum of numbers whose unit digits are X.
- If it is possible, check if N ? X * ( Minimum number of times a number with unit digit X needs to be added to get sum N).
- If the above condition is satisfied then print the minimum number of times a number with unit digit X needs to be added to get sum N. Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate and return// the minimum number of times a number// with unit digit X needs to be added// to get a sum Nint check(int unit_digit, int X){ int times, digit; // Calculate the number of // additions required to get unit // digit of N for (int times = 1; times <= 10; times++) { digit = (X * times) % 10; if (digit == unit_digit) return times; } // If unit digit of N // cannot be obtained return -1;}// Function to return the minimum// number required to represent Nint getNum(int N, int X){ int unit_digit; // Stores unit digit of N unit_digit = N % 10; // Stores minimum addition // of X required to // obtain unit digit of N int times = check(unit_digit, X); // If unit digit of N // cannot be obtained if (times == -1) return times; // Otherwise else { // If N is greater than // or equal to (X*times) if (N >= (times * X)) // Minimum count of numbers // that needed to represent N return times; // Representation not // possible else return -1; }}// Driver Codeint main(){ int N = 58, X = 7; cout << getNum(N, X) << endl; return 0;} |
Java
// Java Program to implement// the above approachclass GFG{ // Function to calculate and return// the minimum number of times a number// with unit digit X needs to be added// to get a sum Nstatic int check(int unit_digit, int X){ int times, digit; // Calculate the number of // additions required to get unit // digit of N for (times = 1; times <= 10; times++) { digit = (X * times) % 10; if (digit == unit_digit) return times; } // If unit digit of N // cannot be obtained return -1;}// Function to return the minimum// number required to represent Nstatic int getNum(int N, int X){ int unit_digit; // Stores unit digit of N unit_digit = N % 10; // Stores minimum addition // of X required to // obtain unit digit of N int times = check(unit_digit, X); // If unit digit of N // cannot be obtained if (times == -1) return times; // Otherwise else { // If N is greater than // or equal to (X*times) if (N >= (times * X)) // Minimum count of numbers // that needed to represent N return times; // Representation not // possible else return -1; }}// Driver Codepublic static void main(String []args){ int N = 58, X = 7; System.out.println( getNum(N, X));}}// This code is contributed by Ritik Bansal |
Python3
# Python3 program to implement# the above approach# Function to calculate and return# the minimum number of times a number# with unit digit X needs to be added# to get a sum Ndef check(unit_digit, X): # Calculate the number of additions # required to get unit digit of N for times in range(1, 11): digit = (X * times) % 10 if (digit == unit_digit): return times # If unit digit of N # cannot be obtained return -1# Function to return the minimum# number required to represent Ndef getNum(N, X): # Stores unit digit of N unit_digit = N % 10 # Stores minimum addition # of X required to # obtain unit digit of N times = check(unit_digit, X) # If unit digit of N # cannot be obtained if (times == -1): return times # Otherwise else: # If N is greater than # or equal to (X*times) if (N >= (times * X)): # Minimum count of numbers # that needed to represent N return times # Representation not # possible else: return -1# Driver CodeN = 58X = 7print(getNum(N, X))# This code is contributed by Sanjit_Prasad |
C#
// C# Program to implement// the above approachusing System;class GFG{ // Function to calculate and return// the minimum number of times a number// with unit digit X needs to be added// to get a sum Nstatic int check(int unit_digit, int X){ int times, digit; // Calculate the number of // additions required to get unit // digit of N for (times = 1; times <= 10; times++) { digit = (X * times) % 10; if (digit == unit_digit) return times; } // If unit digit of N // cannot be obtained return -1;}// Function to return the minimum// number required to represent Nstatic int getNum(int N, int X){ int unit_digit; // Stores unit digit of N unit_digit = N % 10; // Stores minimum addition // of X required to // obtain unit digit of N int times = check(unit_digit, X); // If unit digit of N // cannot be obtained if (times == -1) return times; // Otherwise else { // If N is greater than // or equal to (X*times) if (N >= (times * X)) // Minimum count of numbers // that needed to represent N return times; // Representation not // possible else return -1; }}// Driver Codepublic static void Main(){ int N = 58, X = 7; Console.Write(getNum(N, X));}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript program implementation// of the approach// Function to calculate and return// the minimum number of times a number// with unit digit X needs to be added// to get a sum Nfunction check(unit_digit, X){ let times, digit; // Calculate the number of // additions required to get unit // digit of N for (times = 1; times <= 10; times++) { digit = (X * times) % 10; if (digit == unit_digit) return times; } // If unit digit of N // cannot be obtained return -1;} // Function to return the minimum// number required to represent Nfunction getNum(N, X){ let unit_digit; // Stores unit digit of N unit_digit = N % 10; // Stores minimum addition // of X required to // obtain unit digit of N let times = check(unit_digit, X); // If unit digit of N // cannot be obtained if (times == -1) return times; // Otherwise else { // If N is greater than // or equal to (X*times) if (N >= (times * X)) // Minimum count of numbers // that needed to represent N return times; // Representation not // possible else return -1; }} // Driver Code let N = 58, X = 7; document.write( getNum(N, X)); // This code is contributed by splevel62.</script> |
Output:
4
Time Complexity: O(1)
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!
