Given four integers N, M, A, and B, the task is to print all numbers ( in increasing order ) that can be obtained by adding A or B to N exactly M times.
Examples:
Input: N = 5, M = 3, A = 4, B = 6
Output: 17 19 21 23
Explanation:
Step 1: Adding 4 or 6 to N generates 9 and 11.
Step 2: Adding 4 and 6 to N generates 13, 15, 17.
Step 3: Adding 4 and 6 to N generates 17, 19, 21, 23.Input: N = 8, M = 2, A = 5, B = 10
Output: 18 23 28
Naive Approach: The simplest approach to solve this problem is to use Recursion. In each step, there are only two choices, i.e. to either add A or add B.
Follow the steps below to solve this problem:
- Initialize a Set, say numbers, to store all the numbers that can be made.
- Base case: If M is equal to 0, then the only possible number is N.
- After adding A to N, make a recursive call for M – 1 steps.
- After adding B to N, make a recursive call for M – 1 steps.
- Finally, iterate over the set numbers and print all the numbers.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly N timesvoid possibleNumbers(set<int>& numbers, int N, int M, int A, int B){ // If number of steps is 0 and // only possible number is N if (M == 0) { numbers.insert(N); return; } // Add A to N and make a // recursive call for M - 1 steps possibleNumbers(numbers, N + A, M - 1, A, B); // Add B to N and make a // recursive call for M-1 steps. possibleNumbers(numbers, N + B, M - 1, A, B);}// Driver Codeint main(){ // Given Inputs int N = 5, M = 3, A = 4, B = 6; // Stores all possible numbers set<int> numbers; // Function call possibleNumbers(numbers, N, M, A, B); // Print all possible numbers for (int x : numbers) { cout << x << " "; } return 0;} |
Java
// Java program for the above approachimport java.util.*;public class MyClass{// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly N timesstatic void possibleNumbers(Set<Integer> numbers, int N, int M, int A, int B){ // If number of steps is 0 and // only possible number is N if (M == 0) { numbers.add(N); return; } // Add A to N and make a // recursive call for M - 1 steps possibleNumbers(numbers, N + A, M - 1, A, B); // Add B to N and make a // recursive call for M-1 steps. possibleNumbers(numbers, N + B, M - 1, A, B);}// Driver Code public static void main(String args[]){ // Given Inputs int N = 5, M = 3, A = 4, B = 6; // Stores all possible numbers Set<Integer> numbers = new HashSet<Integer>(); // Function call possibleNumbers(numbers, N, M, A, B); // Print all possible numbers Iterator<Integer> i = numbers.iterator(); while (i.hasNext()) System.out.print(i.next()+ " " );}}// This code is contributed by SoumikMondal |
Python3
# Python3 program for the above approach# Function to find all possible# numbers that can be obtained# by adding A or B to N exactly N timesdef possibleNumbers(numbers, N, M, A, B): # If number of steps is 0 and # only possible number is N if (M == 0): numbers.add(N) return # Add A to N and make a # recursive call for M - 1 steps possibleNumbers(numbers, N + A, M - 1, A, B) # Add B to N and make a # recursive call for M-1 steps. possibleNumbers(numbers, N + B, M - 1, A, B)# Driver Codeif __name__ == '__main__': # Given Inputs N = 5 M = 3 A = 4 B = 6 # Stores all possible numbers numbers = set() # Function call possibleNumbers(numbers, N, M, A, B) # Print all possible numbers for x in numbers: print(x, end = " ") # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class MyClass { // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly N times static void possibleNumbers(HashSet<int> numbers, int N, int M, int A, int B) { // If number of steps is 0 and // only possible number is N if (M == 0) { numbers.Add(N); return; } // Add A to N and make a // recursive call for M - 1 steps possibleNumbers(numbers, N + A, M - 1, A, B); // Add B to N and make a // recursive call for M-1 steps. possibleNumbers(numbers, N + B, M - 1, A, B); } // Driver Code public static void Main(String[] args) { // Given Inputs int N = 5, M = 3, A = 4, B = 6; // Stores all possible numbers HashSet<int> numbers = new HashSet<int>(); // Function call possibleNumbers(numbers, N, M, A, B); // Print all possible numbers foreach(int i in numbers) Console.Write(i + " "); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly N times function possibleNumbers(numbers, N, M, A, B) { // If number of steps is 0 and // only possible number is N if (M == 0) { numbers.add(N); return; } // Add A to N and make a // recursive call for M - 1 steps possibleNumbers(numbers, N + A, M - 1, A, B); // Add B to N and make a // recursive call for M-1 steps. possibleNumbers(numbers, N + B, M - 1, A, B); } // Driver Code // Given Inputs var N = 5, M = 3, A = 4, B = 6; // Stores all possible numbers var numbers = new Set(); // Function call possibleNumbers(numbers, N, M, A, B); // Print all possible numbers for (let x of numbers) { document.write(x+' '); } </script> |
Output:
17 19 21 23
Time Complexity: O(2M)
Auxiliary Space: O(M)
Efficient Approach: This problem has Overlapping Subproblems property and Optimal Substructure property. Therefore, the above approach can be optimized using Dynamic Programming.
Follow the steps below to solve this problem:
- Initialize a vector, say dp[][], and a set, say numbers, where dp[i][j] stores whether the number j is visited or not in i steps.
- Base case: If M is equal to 0, then the only possible number is N.
- If (N+A) has not been obtained at (M-1)th step previously, then after adding A to N, make a recursive call for M – 1 steps and mark dp[M – 1][N + A] as visited.
- If (N + B) has not been obtained at (M – 1)th step previously, then after adding B to N, make a recursive call for M – 1 steps and mark dp[M – 1][N + B] as visited.
- Finally, iterate over the set numbers and print all the numbers.
Below is the implementation of the above approach
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesvoid possibleNumbers(int N, int M, int A, int B){ // For maintaining // increasing order if (A > B) { swap(A, B); } // Smallest number that // can be obtained int number = N + M * A; cout << number << " "; // If A and B are equal, then only // one number can be obtained, i.e. N + M*A if (A != B) { // For finding others numbers, // subtract A from number once // and add B to number once for (int i = 0; i < M; i++) { number = number - A + B; cout << number << " "; } }}// Driver Codeint main(){ // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesstatic void possibleNumbers(int N, int M, int A, int B){ // For maintaining // increasing order if (A > B) { int temp = A; A = B; B = temp; } // Smallest number that // can be obtained int number = N + M * A; System.out.print(number + " "); // If A and B are equal, then only // one number can be obtained, i.e. N + M*A if (A != B) { // For finding others numbers, // subtract A from number once // and add B to number once for(int i = 0; i < M; i++) { number = number - A + B; System.out.print(number + " "); } }}// Driver Codepublic static void main(String[] args) { // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B);} }// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to find all possible# numbers that can be obtained# by adding A or B to N exactly M timesdef possibleNumbers(N, M, A, B): # For maintaining # increasing order if (A > B): temp = A A = B B = temp # Smallest number that # can be obtained number = N + M * A print(number, end = " ") # If A and B are equal, then only # one number can be obtained, i.e. N + M*A if (A != B): # For finding others numbers, # subtract A from number once # and add B to number once for i in range(M): number = number - A + B print(number,end = " ")# Driver Codeif __name__ == '__main__': # Given Input N = 5 M = 3 A = 4 B = 6 # Function Call possibleNumbers(N, M, A, B) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;class GFG{ // Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesstatic void possibleNumbers(int N, int M, int A, int B){ // For maintaining // increasing order if (A > B) { int temp = A; A = B; B = temp; } // Smallest number that // can be obtained int number = N + M * A; Console.Write(number + " "); // If A and B are equal, then only // one number can be obtained, i.e. N + M*A if (A != B) { // For finding others numbers, // subtract A from number once // and add B to number once for(int i = 0; i < M; i++) { number = number - A + B; Console.Write(number + " "); } }}// Driver Codepublic static void Main(String[] args) { // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B);} }// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesfunction possibleNumbers(N,M,A,B){ var i; // For maintaining // increasing order if (A > B) { var temp = A; A = B; B = temp; } // Smallest number that // can be obtained var number = N + M * A; document.write(number + " "); // If A and B are equal, then only // one number can be obtained, i.e. N + M*A if (A != B) { // For finding others numbers, // subtract A from number once // and add B to number once for (i = 0; i < M; i++) { number = number - A + B; document.write(number +" "); } }}// Driver Code // Given Input var N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B); </script> |
Output:
17 19 21 23
Time Complexity: O(M)
Auxiliary Space: O(M*105)
Efficient Approach: The above approach can be further optimized greedily. Follow the steps below to solve this problem:
- If A is greater than B, then swap A and B for maintaining increasing order.
- Initialize a variable, say number as N + M * A, i.e. the smallest number that can be achieved, and print the number.
- If A is not equal to B, then iterate over the range [0, M – 1] using a variable i, and print number – A + B.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesvoid possibleNumbers(int N, int M, int A, int B){ // For maintaining increasing order if (A > B) { swap(A, B); } // Smallest number that can be achieved int number = N + M * A; cout << number << " "; // If A and B are equal, the only number // that can be onbtained is N + M * A if (A != B) { // For finding other numbers, // subtract A from number 1 time // and add B to number 1 time for (int i = 0; i < M; i++) { number = number - A + B; cout << number << " "; } }}// Driver Codeint main(){ // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesstatic void possibleNumbers(int N, int M, int A, int B){ // For maintaining increasing order if (A > B) { int temp = A; A = B; B = temp; } // Smallest number that can be achieved int number = N + M * A; System.out.print(number +" "); // If A and B are equal, the only number // that can be onbtained is N + M * A if (A != B) { // For finding other numbers, // subtract A from number 1 time // and add B to number 1 time for (int i = 0; i < M; i++) { number = number - A + B; System.out.print(number +" "); } }}// Driver Codepublic static void main(String[] args) { // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B);}}// This code is contributed by shivanisinghss2110 |
Python3
# python 3 program for the above approach# Function to find all possible# numbers that can be obtained# by adding A or B to N exactly M timesdef possibleNumbers(N, M, A, B): # For maintaining increasing order if (A > B): temp = A A = B B = temp # Smallest number that can be achieved number = N + M * A print(number,end = " ") # If A and B are equal, the only number # that can be onbtained is N + M * A if (A != B): # For finding other numbers, # subtract A from number 1 time # and add B to number 1 time for i in range(M): number = number - A + B print(number,end= " ")# Driver Codeif __name__ == '__main__': # Given Input N = 5 M = 3 A = 4 B = 6 # Function Call possibleNumbers(N, M, A, B) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesstatic void possibleNumbers(int N, int M, int A, int B){ // For maintaining increasing order if (A > B) { int temp = A; A = B; B = temp; } // Smallest number that can be achieved int number = N + M * A; Console.Write(number +" "); // If A and B are equal, the only number // that can be onbtained is N + M * A if (A != B) { // For finding other numbers, // subtract A from number 1 time // and add B to number 1 time for (int i = 0; i < M; i++) { number = number - A + B; Console.Write(number +" "); } }}// Driver Codepublic static void Main(String[] args) { // Given Input int N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach// Function to find all possible// numbers that can be obtained// by adding A or B to N exactly M timesfunction possibleNumbers( N, M, A, B){ // For maintaining increasing order if (A > B) { var temp = A; A = B; B = temp; } // Smallest number that can be achieved var number = N + M * A; document.write(number +" "); // If A and B are equal, the only number // that can be onbtained is N + M * A if (A != B) { // For finding other numbers, // subtract A from number 1 time // and add B to number 1 time for (var i = 0; i < M; i++) { number = number - A + B; document.write(number +" "); } }}// Driver Code// Given Input var N = 5, M = 3, A = 4, B = 6; // Function Call possibleNumbers(N, M, A, B);// This code is contributed by shivanisinghss2110</script> |
Output:
17 19 21 23
Time Complexity: O(M)
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!
