Given three integers a, b and c. You need to select one integer from the range [a, b] and one integer from the range [b, c] and add them. The task to calculate the number of ways to obtain the sum for all the numbers in the range [1, b+c].
Examples:
Input: a = 1, b = 2, c = 2
Output: 0, 0, 1, 1
Explanation:
The numbers to be obtained are [1, b+c] = [1, 4] = {1, 2, 3, 4}
Therefore, the number of ways to obtain each are:
1 – can’t be obtained
2 – can’t be obtained
3 – only one way. select {1} from range [a, b] and {2} from range [b, c] – 1 + 2 = 3
4 – only one way. select {2} from range [a, b] and {2} from range [b, c] – 2 + 2 = 4Input: a = 1, b = 3, c = 4
Output: 0, 0, 0, 1, 2, 2, 1
Simple Approach:
- A simple brute force solution will be to use a nested loop where exterior loop traverses from i = a to i = b and inner loop from j = b to j = c inclusive.
- We will initialise array a of size b + c + 1 with zero. Now in loops, we will increment the index at i+j, i.e., (a[i+j]++).
- We will simply print the array at the end.
Below is the implementation of the above approach.
C++
// C++ program to calculate// the number of ways#include <bits/stdc++.h>using namespace std;void CountWays(int a, int b, int c){ int x = b + c + 1; int arr[x] = { 0 }; // Initialising the array with zeros. // You can do using memset too. for (int i = a; i <= b; i++) { for (int j = b; j <= c; j++) { arr[i + j]++; } } // Printing the array for (int i = 1; i < x; i++) { cout << arr[i] << " "; } cout << endl;}// Driver codeint main(){ int a = 1; int b = 2; int c = 2; CountWays(a, b, c); return 0;} |
Java
// Java program to calculate // the number of ways import java.io.*;public class GFG{ public static void CountWays(int a, int b, int c) { int x = b + c + 1; int[] arr = new int[x]; // Initialising the array with zeros. // You can do using memset too. for(int i = a; i <= b; i++) { for(int j = b; j <= c; j++) { arr[i + j]++; } } // Printing the array for(int i = 1; i < x; i++) { System.out.print(arr[i] + " "); } } // Driver codepublic static void main(String[] args){ int a = 1; int b = 2; int c = 2; CountWays(a, b, c); }}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to calculate# the number of waysdef CountWays(a, b, c): x = b + c + 1; arr = [0] * x; # Initialising the array with zeros. # You can do using memset too. for i in range(a, b + 1): for j in range(b, c + 1): arr[i + j] += 1; # Printing the array for i in range(1, x): print(arr[i], end = " "); # Driver codeif __name__ == '__main__': a = 1; b = 2; c = 2; CountWays(a, b, c); # This code is contributed by Rajput-Ji |
C#
// C# program to calculate // the number of ways using System;class GFG{ public static void CountWays(int a, int b, int c) { int x = b + c + 1; int[] arr = new int[x]; // Initialising the array with zeros. // You can do using memset too. for(int i = a; i <= b; i++) { for(int j = b; j <= c; j++) { arr[i + j]++; } } // Printing the array for(int i = 1; i < x; i++) { Console.Write(arr[i] + " "); } } // Driver code public static void Main() { int a = 1; int b = 2; int c = 2; CountWays(a, b, c); } } // This code is contributed by rutvik_56 |
Javascript
<script> // Javascript program to calculate // the number of ways function CountWays(a, b, c) { let x = b + c + 1; let arr = new Array(x); arr.fill(0); // Initialising the array with zeros. // You can do using memset too. for (let i = a; i <= b; i++) { for (let j = b; j <= c; j++) { arr[i + j]++; } } // Printing the array for (let i = 1; i < x; i++) { document.write(arr[i] + " "); } document.write("</br>"); } // Driver code let a = 1; let b = 2; let c = 2; CountWays(a, b, c); </script> |
0 0 1 1
Time Complexity: O((b-a)*(c-b)), which in the worst case is O(c2)
Auxiliary Space: O(x), as We are using extra space.
Efficient Approach: The idea is to use Prefix Sum logic to solve this problem.
- We will traverse i from [a, b] and for every i we will simply increment the value of starting interval arr[i + b] by 1 and decrement the value of ending interval arr[i + c + 1] by 1.
- Now all we need to do is to calculate the prefix sum of the array ( arr[i]+ = arr[i-1] ) and print the array.
Lets see the approach with the help of an example.
Why does this work?
For example: a = 1, b = 2, c = 2, we will encounter only two values of i
i = 1 = > arr[1+2]++; arr[1+2+1]–;
i = 2 = > arr[2+2]++; arr[2+2+1]–;
arr = {0, 0, 0, 1, 0, -1};
prefix sums:
arr = {0, 0, 0, 1, 1, 0};
Now carefully look and realise that this is our answer.
So what we do at particular index i is arr[i+b]++ and arr[i+c+1]–;
Now we are using prefix sums so all the values will be incremented by 1 between i+b and infinite(We won’t go there but will result in prefix sum increment by 1 and as soon as we do a decrement at i+c+1 all the values between i+c+1 and infinite will be decreased by one.
So effectively all the values in the range [i+b, i+c] are incremented by one, and rest all the values will remain unaffected.
Below is the implementation of the above approach.
C++
// C++ program to calculate// the number of ways#include <bits/stdc++.h>using namespace std;void CountWays(int a, int b, int c){ // 2 is added because sometimes // we will decrease the // value out of bounds. int x = b + c + 2; // Initialising the array with zeros. // You can do using memset too. int arr[x] = { 0 }; for (int i = 1; i <= b; i++) { arr[i + b]++; arr[i + c + 1]--; } // Printing the array for (int i = 1; i < x - 1; i++) { arr[i] += arr[i - 1]; cout << arr[i] << " "; } cout << endl;}// Driver codeint main(){ int a = 1; int b = 2; int c = 2; CountWays(a, b, c); return 0;} |
Java
// Java program to calculate// the number of waysimport java.io.*;class GFG{static void CountWays(int a, int b, int c){ // 2 is added because sometimes // we will decrease the // value out of bounds. int x = b + c + 2; // Initialising the array with zeros. int arr[] = new int[x]; for(int i = 1; i <= b; i++) { arr[i + b]++; arr[i + c + 1]--; } // Printing the array for(int i = 1; i < x - 1; i++) { arr[i] += arr[i - 1]; System.out.print(arr[i] + " "); } System.out.println();}// Driver codepublic static void main(String[] args){ int a = 1; int b = 2; int c = 2; CountWays(a, b, c);}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to calculate# the number of waysdef CountWays(a, b, c): # 2 is added because sometimes # we will decrease the # value out of bounds. x = b + c + 2; # Initialising the array with zeros. arr = [0] * x; for i in range(1, b+1): arr[i + b] = arr[i + b] + 1; arr[i + c + 1] = arr[i + c + 1] -1; # Printing the array for i in range(1, x-1): arr[i] += arr[i - 1]; print(arr[i], end = " "); # Driver codeif __name__ == '__main__': a = 1; b = 2; c = 2; CountWays(a, b, c); # This code is contributed by rock_cool |
C#
// C# program to calculate// the number of waysusing System;class GFG{static void CountWays(int a, int b, int c){ // 2 is added because sometimes // we will decrease the // value out of bounds. int x = b + c + 2; // Initialising the array with zeros. int []arr = new int[x]; for(int i = 1; i <= b; i++) { arr[i + b]++; arr[i + c + 1]--; } // Printing the array for(int i = 1; i < x - 1; i++) { arr[i] += arr[i - 1]; Console.Write(arr[i] + " "); } Console.WriteLine();}// Driver codepublic static void Main(){ int a = 1; int b = 2; int c = 2; CountWays(a, b, c);}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript program to calculate// the number of waysfunction CountWays(a, b, c){ // 2 is added because sometimes // we will decrease the // value out of bounds. let x = b + c + 2; // Initialising the array with zeros. // You can do using memset too. let arr = new Array(x); arr.fill(0); for(let i = 1; i <= b; i++) { arr[i + b]++; arr[i + c + 1]--; } // Printing the array for(let i = 1; i < x - 1; i++) { arr[i] += arr[i - 1]; document.write(arr[i] + " "); } document.write("</br>");}// Driver codelet a = 1;let b = 2;let c = 2;CountWays(a, b, c);// This code is contributed by rameshtravel07 </script> |
0 0 1 1
Time complexity: O(b+c), as we are using loop to traverse b+c times.
Auxiliary Space: O(b+c), as we are using extra space.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
