Number of solutions for the equation x + y + z <= n

0 0 7 minutes read

Given four numbers x, y, z, n. The task is to find the number of solutions for the equation x + y + z <= n, such that 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.

Examples:

Input: x = 1, y = 1, z = 1, n = 1
Output: 4

Input: x = 1, y = 2, z = 3, n = 4
Output: 20

Approach: Let’s iterate explicitly over all possible values of x and y (using nested loop). For one such fixed values of x and y, the problem reduces to how many values of z are there such that z <= n – x – y and 0 <= z <= Z.

Below is the required implementation to find the number of solutions:

C++

// CPP program to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
#include <bits/stdc++.h>
using namespace std;
 
// function to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
int NumberOfSolutions(int x, int y, int z, int n)
{
    // to store answer
    int ans = 0;
 
    // for values of x
    for (int i = 0; i <= x; i++) {
 
        // for values of y
        for (int j = 0; j <= y; j++) {
 
            // maximum possible value of z
            int temp = n - i - j;
 
            // if z value greater than equals to 0
            // then only it is valid
            if (temp >= 0) {
 
                // find minimum of temp and z
                temp = min(temp, z);
                ans += temp + 1;
            }
        }
    }
 
    // return required answer
    return ans;
}
 
// Driver code
int main()
{
    int x = 1, y = 2, z = 3, n = 4;
 
    cout << NumberOfSolutions(x, y, z, n);
 
    return 0;
}

C

// C program to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
#include <stdio.h>
 
int min(int a, int b)
{
  int min = a;
  if(min > b)
    min = b;
  return min;
}
 
// function to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
int NumberOfSolutions(int x, int y, int z, int n)
{
    // to store answer
    int ans = 0;
 
    // for values of x
    for (int i = 0; i <= x; i++) {
 
        // for values of y
        for (int j = 0; j <= y; j++) {
 
            // maximum possible value of z
            int temp = n - i - j;
 
            // if z value greater than equals to 0
            // then only it is valid
            if (temp >= 0) {
 
                // find minimum of temp and z
                temp = min(temp, z);
                ans += temp + 1;
            }
        }
    }
 
    // return required answer
    return ans;
}
 
// Driver code
int main()
{
    int x = 1, y = 2, z = 3, n = 4;
   
    printf("%d",NumberOfSolutions(x, y, z, n));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

Java

// Java program to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
 
import java.io.*;
 
class GFG {
 
// function to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
static int NumberOfSolutions(int x, int y, int z, int n)
{
    // to store answer
    int ans = 0;
 
    // for values of x
    for (int i = 0; i <= x; i++) {
 
        // for values of y
        for (int j = 0; j <= y; j++) {
 
            // maximum possible value of z
            int temp = n - i - j;
 
            // if z value greater than equals to 0
            // then only it is valid
            if (temp >= 0) {
 
                // find minimum of temp and z
                temp = Math.min(temp, z);
                ans += temp + 1;
            }
        }
    }
 
    // return required answer
    return ans;
}
 
       // Driver code
    public static void main (String[] args) {
     
    int x = 1, y = 2, z = 3, n = 4;
    System.out.println( NumberOfSolutions(x, y, z, n));
 
    }
}
 
// this code is contributed by anuj_67..

Python 3

# Python3 program to find the number  
# of solutions for the equation
# x + y + z <= n, such that 
# 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z. 
 
# function to find the number of solutions
# for the equation x + y + z <= n, such that 
# 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z. 
def NumberOfSolutions(x, y, z, n) :
 
    # to store answer
    ans = 0
 
    # for values of x 
    for i in range(x + 1) :
 
        # for values of y 
        for j in range(y + 1) :
 
            # maximum possible value of z 
            temp = n - i - j
 
            # if z value greater than equals  
            # to 0 then only it is valid 
            if temp >= 0 :
 
                # find minimum of temp and z
                temp = min(temp, z)
                ans += temp + 1
 
    # return required answer
    return ans
 
# Driver code
if __name__ == "__main__" :
 
    x, y, z, n = 1, 2, 3, 4
     
    # function calling
    print(NumberOfSolutions(x, y, z, n))
 
# This code is contributed by ANKITRAI1

C#

// C# program to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
using System;
 
public class GFG{
     
     
// function to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
static int NumberOfSolutions(int x, int y, int z, int n)
{
    // to store answer
    int ans = 0;
 
    // for values of x
    for (int i = 0; i <= x; i++) {
 
        // for values of y
        for (int j = 0; j <= y; j++) {
 
            // maximum possible value of z
            int temp = n - i - j;
 
            // if z value greater than equals to 0
            // then only it is valid
            if (temp >= 0) {
 
                // find minimum of temp and z
                temp = Math.Min(temp, z);
                ans += temp + 1;
            }
        }
    }
 
    // return required answer
    return ans;
}
 
// Driver code
 
     
     
    static public void Main (){
         
    int x = 1, y = 2, z = 3, n = 4;
 
    Console.WriteLine( NumberOfSolutions(x, y, z, n));
 
    }
}
 
// This code is contributed by anuj_67..

PHP

<?php
// PHP program to find the number 
// of solutions for the equation 
// x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
 
// function to find the number of 
// solutions for the equation 
// x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
function NumberOfSolutions($x, $y, $z, $n)
{
    // to store answer
    $ans = 0;
 
    // for values of x
    for ($i = 0; $i <= $x; $i++)
    {
 
        // for values of y
        for ($j = 0; $j <= $y; $j++)
        {
 
            // maximum possible value of z
            $temp = $n - $i - $j;
 
            // if z value greater than equals 
            // to 0 then only it is valid
            if ($temp >= 0)
            {
 
                // find minimum of temp and z
                $temp = min($temp, $z);
                $ans += $temp + 1;
            }
        }
    }
 
    // return required answer
    return $ans;
}
 
// Driver code
$x = 1; $y = 2; 
$z = 3; $n = 4;
 
echo NumberOfSolutions($x, $y, $z, $n);
 
// This code is contributed 
// by Akanksha Rai(Abby_akku)
?>

Javascript

<script>
 
// Javascript program to find the number
// of solutions for the equation x + y + z <= n,
// such that 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
 
// Function to find the number of solutions for
// the equation x + y + z <= n, such that
// 0 <= x <= X, 0 <= y <= Y, 0 <= z <= Z.
function NumberOfSolutions(x, y, z, n)
{
     
    // To store answer
    var ans = 0;
 
    // for values of x
    for(var i = 0; i <= x; i++) 
    {
         
        // for values of y
        for(var j = 0; j <= y; j++) 
        {
             
            // Maximum possible value of z
            var temp = n - i - j;
 
            // If z value greater than equals to 0
            // then only it is valid
            if (temp >= 0) 
            {
                 
                // Find minimum of temp and z
                temp = Math.min(temp, z);
                ans += temp + 1;
            }
        }
    }
     
    // Return required answer
    return ans;
}
 
// Driver Code 
var x = 1, y = 2, z = 3, n = 4;
 
document.write(NumberOfSolutions(x, y, z, n));
 
// This code is contributed by Ankita saini
     
</script>

Output:

Time Complexity: O(x * y)
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 zambiatek!