Número de soluciones para x < y, donde a <= x <= b y c <= y <= d y x, y son números enteros

Dados cuatro enteros a, b, c, d (hasta 10^6). La tarea es encontrar el número de soluciones para x < y, donde a <= x <= b y c <= y <= d y x, y enteros. 
Ejemplos : 
 

Input: a = 2, b = 3, c = 3, d = 4
Output: 3

Input: a = 3, b = 5, c = 6, d = 7
Output: 6

Enfoque: vamos a iterar explícitamente sobre todos los valores posibles de x. Para uno de esos valores fijos de x, el problema se reduce a cuántos valores de y hay tales que c <= y <= d y x = max(c, x + 1) y y <= d . Supongamos que c <= d , de lo contrario, no hay valores válidos de y, por supuesto. De ello se deduce que para una x fija, hay d – max(c, x+1) + 1 valores válidos de y porque el número de enteros en un rango [R1, R2] viene dado por R2 – R1 + 1.
A continuación es la implementación del enfoque anterior: 
 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to Find the number of solutions for x < y,
// where a <= x <= b and c <= y <= d and x, y integers.
int NumberOfSolutions(int a, int b, int c, int d)
{
    // to store answer
    int ans = 0;
 
    // iterate explicitly over all possible values of x
    for (int i = a; i <= b; i++)
        if (d >= max(c, i + 1))
            ans += d - max(c, i + 1) + 1;
 
    // return answer
    return ans;
}
 
// Driver code
int main()
{
    int a = 2, b = 3, c = 3, d = 4;
 
    // function call
    cout << NumberOfSolutions(a, b, c, d);
 
    return 0;
}

// C implementation of above approach
#include <stdio.h>
 
int max(int a, int b)
{
  int max = a;
  if(max < b)
    max = b;
  return max;
}
 
// function to Find the number of solutions for x < y,
// where a <= x <= b and c <= y <= d and x, y integers.
int NumberOfSolutions(int a, int b, int c, int d)
{
    // to store answer
    int ans = 0;
 
    // iterate explicitly over all possible values of x
    for (int i = a; i <= b; i++)
        if (d >= max(c, i + 1))
            ans += d - max(c, i + 1) + 1;
 
    // return answer
    return ans;
}
 
// Driver code
int main()
{
    int a = 2, b = 3, c = 3, d = 4;
 
    // function call
    printf("%d",NumberOfSolutions(a, b, c, d));
 
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java implementation of above approach
import java.io.*;
 
class GFG
{
 
// function to Find the number of
// solutions for x < y, where
// a <= x <= b and c <= y <= d
// and x, y integers.
static int NumberOfSolutions(int a, int b,
                             int c, int d)
{
    // to store answer
    int ans = 0;
 
    // iterate explicitly over all
    // possible values of x
    for (int i = a; i <= b; i++)
        if (d >= Math.max(c, i + 1))
            ans += d - Math.max(c, i + 1) + 1;
 
    // return answer
    return ans;
}
 
// Driver code
public static void main (String[] args)
{
    int a = 2, b = 3, c = 3, d = 4;
 
    // function call
    System.out.println(NumberOfSolutions(a, b, c, d));
}
}
 
// This code is contributed
// by inder_verma

# Python3 implementation of
# above approach
 
# function to Find the number of
# solutions for x < y, where
# a <= x <= b and c <= y <= d and
# x, y integers.
def NumberOfSolutions(a, b, c, d) :
 
    # to store answer
    ans = 0
 
    # iterate explicitly over all
    # possible values of x
    for i in range(a, b + 1) :
 
        if d >= max(c, i + 1) :
 
            ans += d - max(c, i + 1) + 1
 
    # return answer
    return ans
 
# Driver code
if __name__ == "__main__" :
 
    a, b, c, d = 2, 3, 3, 4
 
    # function call
    print(NumberOfSolutions(a, b, c, d))
 
# This code is contributed by ANKITRAI1

// C# implementation of above approach
using System;
 
class GFG
{
 
// function to Find the number of
// solutions for x < y, where
// a <= x <= b and c <= y <= d
// and x, y integers.
static int NumberOfSolutions(int a, int b,
                              int c, int d)
{
    // to store answer
    int ans = 0;
 
    // iterate explicitly over all
    // possible values of x
    for (int i = a; i <= b; i++)
        if (d >= Math.Max(c, i + 1))
            ans += d - Math.Max(c, i + 1) + 1;
 
    // return answer
    return ans;
}
 
// Driver code
public static void Main()
{
    int a = 2, b = 3, c = 3, d = 4;
 
    // function call
    Console.WriteLine(NumberOfSolutions(a, b, c, d));
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP implementation of above approach
 
// function to Find the number
// of solutions for x < y, where
// a <= x <= b and c <= y <= d
// and x, y integers.
function NumberOfSolutions($a, $b, $c, $d)
{
    // to store answer
    $ans = 0;
 
    // iterate explicitly over all
    // possible values of x
    for ($i = $a; $i <= $b; $i++)
        if ($d >= max($c, $i + 1))
            $ans += $d - max($c, $i + 1) + 1;
 
    // return answer
    return $ans;
}
 
// Driver code
$a = 2; $b = 3; $c = 3; $d = 4;
 
// function call
echo NumberOfSolutions($a, $b, $c, $d);
 
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>

<script>
 
// Javascript implementation of above approach
 
// function to Find the number of
// solutions for x < y, where
// a <= x <= b and c <= y <= d
// and x, y integers.
function NumberOfSolutions(a, b, c, d)
{
    // to store answer
    let ans = 0;
 
    // iterate explicitly over all
    // possible values of x
    for (let i = a; i <= b; i++)
        if (d >= Math.max(c, i + 1))
            ans += d - Math.max(c, i + 1) + 1;
 
    // return answer
    return ans;
}
 
// Driver Code
 
    let a = 2, b = 3, c = 3, d = 4;
 
    // function call
    document.write(NumberOfSolutions(a, b, c, d));
            
</script>

3

Complejidad temporal: O(ba) donde a y b son los números enteros dados.
Espacio Auxiliar: O(1)