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 a 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 1:
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:
- Subtracting the value D from the value of N.
- Check if the updated value of N contains digit D or not. If found to be true, then print “Yes” and break out of the loop.
- After completing the above steps, if none of the above conditions satisfies, then print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to check if N contains// digit D in itbool findDigit(int N, int D){ // Iterate until N is positive while (N > 0) { // Find the last digit int a = N % 10; // If the last digit is the // same as digit D if (a == D) { return true; } N /= 10; } // Return false return false;}// Function to check if the value of// N can be represented as sum of// integers having digit d in itbool check(int N, int D){ // Iterate until N is positive while (N > 0) { // Check if N contains digit // D or not if (findDigit(N, D) == true) { return true; } // Subtracting D from N N -= D; } // Return false return false;}// Driver Codeint main(){ int N = 24; int D = 7; if (check(N, D)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
// Java approach for the above approachimport java.util.*;class GFG{// Function to check if N contains// digit D in itstatic boolean findDigit(int N, int D){ // Iterate until N is positive while (N > 0) { // Find the last digit int a = N % 10; // If the last digit is the // same as digit D if (a == D) { return true; } N /= 10; } // Return false return false;}// Function to check if the value of// N can be represented as sum of// integers having digit d in itstatic boolean check(int N, int D){ // Iterate until N is positive while (N > 0) { // Check if N contains digit // D or not if (findDigit(N, D) == true) { return true; } // Subtracting D from N N -= D; } // Return false return false;} // Driver Codepublic static void main(String[] args){ int N = 24; int D = 7; if (check(N, D)) { System.out.print("Yes"); } else { System.out.print("No"); }}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to check if N contains# digit D in itdef findDigit(N, D): # Iterate until N is positive while (N > 0): # Find the last digit a = N % 10 # If the last digit is the # same as digit D if (a == D): return True N /= 10 # Return false return False# Function to check if the value of# N can be represented as sum of# integers having digit d in itdef check(N, D): # Iterate until N is positive while (N > 0): # Check if N contains digit # D or not if (findDigit(N, D) == True): return True # Subtracting D from N N -= D # Return false return False# Driver Codeif __name__ == '__main__': N = 24 D = 7 if (check(N, D)): print("Yes") else: print("No")# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System; class GFG{ // Function to check if N contains// digit D in itstatic bool findDigit(int N, int D){ // Iterate until N is positive while (N > 0) { // Find the last digit int a = N % 10; // If the last digit is the // same as digit D if (a == D) { return true; } N /= 10; } // Return false return false;} // Function to check if the value of// N can be represented as sum of// integers having digit d in itstatic bool check(int N, int D){ // Iterate until N is positive while (N > 0) { // Check if N contains digit // D or not if (findDigit(N, D) == true) { return true; } // Subtracting D from N N -= D; } // Return false return false;} // Driver Codepublic static void Main(){ int N = 24; int D = 7; if (check(N, D)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by code_hunt. |
Javascript
<script>// javascript program for the above approach// Function to check if N contains// digit D in itfunction findDigit(N, D){ // Iterate until N is positive while (N > 0) { // Find the last digit let a = N % 10; // If the last digit is the // same as digit D if (a == D) { return true; } N = Math.floor(N / 10); } // Return false return false;} // Function to check if the value of// N can be represented as sum of// integers having digit d in itfunction check(N, D){ // Iterate until N is positive while (N > 0) { // Check if N contains digit // D or not if (findDigit(N, D) == true) { return true; } // Subtracting D from N N -= D; } // Return false return false;}// Driver Code let N = 24; let D = 7; if (check(N, D)) { document.write("Yes"); } else { document.write("No"); }</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach 2: Dynamic Programming
We can solve this problem using Dynamic Programming (DP). We can create a DP array of size N+1, where DP[i] stores whether it is possible to represent i as the sum of numbers having the digit D in them or not. We can initialize DP[0] as true since it is always possible to represent 0 as the sum of no numbers.
Then, for each i from 1 to N, we can check if i contains the digit D. If it does, then we can mark DP[i] as true. Otherwise, we can iterate over all possible j < i such that DP[j] is true, and check if i-j contains the digit D. If it does, then we can mark DP[i] as true.
At the end, we can check if DP[N] is true or not. If it is, then we can say that N can be represented as the sum of numbers having the digit D in them. Otherwise, we can say that it is not possible.
C++
#include <cstring>#include <iostream>using namespace std;bool check(int N, int D){ // Create DP array bool DP[N + 1]; // Initialize DP[0] memset(DP, false, sizeof(DP)); DP[0] = true; // Fill DP array for (int i = 1; i <= N; i++) { // Check if i contains digit D if (i % 10 == D || i / 10 == D) { DP[i] = true; continue; } // Iterate over all j < i such that DP[j] is true for (int j = 1; j < i; j++) { if (DP[j] && ((i - j) % 10 == D || (i - j) / 10 == D)) { DP[i] = true; break; } } } // Return DP[N] return DP[N];}// Driver Codeint main(){ int N = 24; int D = 7; if (check(N, D)) { cout << "Yes"; } else { cout << "No"; } return 0;} |
Java
import java.util.Arrays;public class Main { static boolean check(int N, int D) { // Create DP array boolean[] DP = new boolean[N + 1]; // Initialize DP[0] Arrays.fill(DP, false); DP[0] = true; // Fill DP array for (int i = 1; i <= N; i++) { // Check if i contains digit D if (i % 10 == D || i / 10 == D) { DP[i] = true; continue; } // Iterate over all j < i such that DP[j] is true for (int j = 1; j < i; j++) { if (DP[j] && ((i - j) % 10 == D || (i - j) / 10 == D)) { DP[i] = true; break; } } } // Return DP[N] return DP[N]; } // Driver Code public static void main(String[] args) { int N = 24; int D = 7; if (check(N, D)) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
def check(N, D): # Create DP array DP = [False] * (N + 1) # Initialize DP[0] DP[0] = True # Fill DP array for i in range(1, N+1): # Check if i contains digit D if i % 10 == D or i // 10 == D: DP[i] = True continue # Iterate over all j < i such that DP[j] is true for j in range(1, i): if DP[j] and ((i - j) % 10 == D or (i - j) // 10 == D): DP[i] = True break # Return DP[N] return DP[N]# Driver codeN = 24D = 7if check(N, D): print("Yes")else: print("No") |
C#
using System;namespace ConsoleApp {class Program { static bool Check(int N, int D) { // Create DP array bool[] DP = new bool[N + 1]; // Initialize DP[0] for (int i = 0; i < DP.Length; i++) { DP[i] = false; } DP[0] = true; // Fill DP array for (int i = 1; i <= N; i++) { // Check if i contains digit D if (i % 10 == D || i / 10 == D) { DP[i] = true; continue; } // Iterate over all j < i such that DP[j] is // true for (int j = 1; j < i; j++) { if (DP[j] && ((i - j) % 10 == D || (i - j) / 10 == D)) { DP[i] = true; break; } } } // Return DP[N] return DP[N]; } // Driver Code static void Main(string[] args) { int N = 24; int D = 7; if (Check(N, D)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } Console.ReadKey(); }}}//This code is contributed by sarojmcy2e |
Javascript
function check(N, D) { let DP = new Array(N + 1).fill(false); DP[0] = true; for (let i = 1; i <= N; i++) { if (i % 10 === D || Math.floor(i / 10) === D) { DP[i] = true; continue; } for (let j = 1; j < i; j++) { if (DP[j] && ((i - j) % 10 === D || Math.floor((i - j) / 10) === D)) { DP[i] = true; break; } } } return DP[N];}let N = 24;let D = 7;if (check(N, D)) { console.log("Yes");} else { console.log("No");} |
Output
Yes
Time Complexity: O(N^(1/3)log(N)), where N is the input number.
Auxiliary Space: O(N^(1/3)), since we are storing all perfect cubes up to N^(1/3) in the map.
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!
