Friday, September 22, 2023
HomeSoftware DevelopmentVerify if a quantity may be represented because the sum of numbers...

# Verify if a quantity may be represented because the sum of numbers with no less than one digit equal to Ok

Given integers N and K, the task is to check if a number can be represented as the sum of numbers that have at least one digit equal to K.

Example:

Input: N = 68, K = 7
Output: YES
Explanation: 68 = (27 + 17 + 17 + 7). Each number has atleast one digit equal to 7.

Input: N = 23, K = 3
Output: YES
Explanation: 23 itself contains a digit equal to 3.

Approach: The given problem can be solved by using simple concepts of math. Follow the steps below to solve the problem:

• Initialize a variable temp to k, and also take a counter say count, assign it with 0
• Iterate till the last digits of temp and N are not equal and at each iteration
• Increment the value of temp by k
• Keep a count of iterations and break the loop if the count becomes greater than 10
• Check if the last digits of temp and N are equal, and if the value of temp <= N:
• If the above condition is satisfied return true
• Else return false
• Also if k * 10 <= N, return true
• Else return false

Below is the implementation of the above approach:

## C++

 `#include ``using` `namespace` `std;` `bool` `checkEqualtoSum(``int` `N, ``int` `k)``{``    ``    ``    ``int` `temp = k;``    ` `    ``    ``int` `count = 0;``    ` `    ``    ``    ``    ``while``(count <= 10 &&``                  ``N % 10 != temp % 10) {``      ` `        ``temp += k;``        ``count++;``    ``}``    ` `    ``    ``    ``    ``if``(N % 10 == temp % 10 && temp <= N)``        ``return` `true``;``    ` `    ``    ``if``(k * 10 <= N)``        ``return` `true``;``    ` `    ``    ``return` `false``;``}` `int` `main()``{``    ``int` `N = 68;``    ``int` `K = 7;` `      ``    ``if``(checkEqualtoSum(N, K))``          ``cout << ``"YES"``;``    ``else` `cout << ``"NO"``;``    ` `    ``return` `0;``}`

## Python3

 `def` `checkEqualtoSum(N, k):` `    ``    ``    ``temp ``=` `k` `    ``    ``count ``=` `0` `    ``    ``    ``    ``while``(count <``=` `10` `and` `N ``%` `10` `!``=` `temp ``%` `10``):` `        ``temp ``+``=` `k``        ``count ``+``=` `1` `    ``    ``    ``    ``if``(N ``%` `10` `=``=` `temp ``%` `10` `and` `temp <``=` `N):``        ``return` `True` `    ``    ``if``(k ``*` `10` `<``=` `N):``        ``return` `True` `    ``    ``return` `False`  `if` `__name__ ``=``=` `"__main__"``:` `    ``N ``=` `68``    ``K ``=` `7` `    ``    ``if``(checkEqualtoSum(N, K)):``        ``print``(``"YES"``)``    ``else``:``        ``print``(``"NO"``)` `    `

Time Complexity: O(1)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

RELATED ARTICLES