Check if N can be represented as sum of positive integers containing digit D at least once

Check if N can be represented as sum of positive integers containing digit D at least once

Given a positive integer N and a digit D, the task is to check if N can be represented as a sum of positive integers containing the digit D at least once. If it is possible to represent N in such format, then print “Yes”. Otherwise, print “No”.

Examples:

Input: N = 24, D = 7
Output: Yes
Explanation: The value 24 can be represented as 17 + 7, both containing the digit 7.

Input: N = 27 D = 2
Output: Yes

Approach: Follow the steps to solve the problem:

• Check if the given N contains digit D or not. If found to be true, then print “Yes”.
• Otherwise, iterate until N is greater than 0 and perform the following steps:
• After completing the above steps, if none of the above conditions satisfies, then print “No”.

Below is the implementation of the above approach:

C++

#include <iostream> using namespace std;    bool findDigit(int N, int D) {          while (N > 0) {                     int a = N % 10;                              if (a == D) {             return true;         }            N /= 10;     }             return false; }    bool check(int N, int D) {          while (N > 0) {                              if (findDigit(N, D) == true) {             return true;         }                     N -= D;     }             return false; }    int main() {     int N = 24;     int D = 7;     if (check(N, D)) {         cout << "Yes";     }     else {         cout << "No";     }        return 0; }

Output:

Yes

Time Complexity: O(N)
Space Complexity: 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.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets