Number of ways to obtain each numbers in range [1, b+c] by adding any two numbers in range [a, b] and [b, c]

0 0 7 minutes read

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 = 4

Input: 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 code
int 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 code
public 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 ways
def 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 code
if __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>

Output:

0 0 1 1

Time Complexity: O((b-a)*(c-b)), which in the worst case is O(c²)
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 code
int 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.*;
 
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 code
public 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 ways
def 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 code
if __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 ways
using 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 code
public 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 ways
function 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 code
let a = 1;
let b = 2;
let c = 2;
 
CountWays(a, b, c);
 
// This code is contributed by rameshtravel07  
 
</script>

Output:

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.

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 zambiatek!