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 times void 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 Code int 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 approach import java.util.*; 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(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 times def 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 if __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 approach using 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> |
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 times void 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 Code int 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 approach import java.util.*; class GFG{ // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly M times static 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 Code public 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 times def 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 Code if __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 approach using System; class GFG{ // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly M times static 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 Code public 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 times function 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> |
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 times void 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 Code int 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 approach import java.util.*; class GFG { // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly M times static 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 Code public 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 times def 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 Code if __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 approach using System; class GFG { // Function to find all possible // numbers that can be obtained // by adding A or B to N exactly M times static 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 Code public 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 times function 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> |
17 19 21 23
Time Complexity: O(M)
Auxiliary Space: O(1)