Contar el número de billetes necesarios

Tienes una cantidad ilimitada de billetes por valor de dólares   A y  B ( A no es igual a B) . Quiere pagar un total de  S dólares utilizando exactamente  N  billetes. La tarea es encontrar el número de billetes que valen  A  dólares que necesitas. Si no hay solución devuelve  -1 .

Ejemplos: 

Entrada: A = 1, B = 2, S = 7, N = 5 
Salida: 3 
3 * A + 2 * B = S 
3 * 1 + 2 * 2 = 7

Entrada: A = 2, B = 1, S = 7, N = 5 
Salida: 2

Entrada: A = 2, B = 1, S = 4, N = 5 
Salida: -1

Entrada: A = 2, B = 3, S = 20, N = 8 
Salida: 4 

Enfoque: Sea x el número de billetes de valor A necesarios y luego el resto de los billetes, es decir , N – x debe ser de valor B. Dado que se requiere que su suma sea S , entonces se debe satisfacer la siguiente ecuación:  

S = (A * x) + (B * (N – x)) 
Resolviendo más la ecuación, 
S = (A * x) + (B * N) – (B * x) 
S – (B * N) = ( A – B) * x 
x = (S – (B * N)) / (A – B) 
Después de resolver para x , es el número de notas de valor A requeridas 
solo si el valor de x es un número entero, de lo contrario el resultado no es posible. 
 

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to return the amount of notes
// with value A required
int bankNotes(int A, int B, int S, int N)
{
    int numerator = S - (B * N);
    int denominator = A - B;
 
    // If possible
    if (numerator % denominator == 0)
        return (numerator / denominator);
    return -1;
}
 
// Driver code
int main()
{
    int A = 1, B = 2, S = 7, N = 5;
    cout << bankNotes(A, B, S, N) << endl;
}
     
// This code is contributed by mits

// Java implementation of the approach
class GFG {
 
    // Function to return the amount of notes
    // with value A required
    static int bankNotes(int A, int B, int S, int N)
    {
        int numerator = S - (B * N);
        int denominator = A - B;
 
        // If possible
        if (numerator % denominator == 0)
            return (numerator / denominator);
        return -1;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int A = 1, B = 2, S = 7, N = 5;
        System.out.print(bankNotes(A, B, S, N));
    }
}

# Python3 implementation of the approach
 
# Function to return the amount of notes
# with value A required
def bankNotes(A, B, S, N):
 
    numerator = S - (B * N)
    denominator = A - B
 
    # If possible
    if (numerator % denominator == 0):
        return (numerator // denominator)
    return -1
 
# Driver code
A, B, S, N = 1, 2, 7, 5
print(bankNotes(A, B, S, N))
 
# This code is contributed
# by mohit kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Function to return the amount of notes
    // with value A required
    static int bankNotes(int A, int B,
                         int S, int N)
    {
        int numerator = S - (B * N);
        int denominator = A - B;
 
        // If possible
        if (numerator % denominator == 0)
            return (numerator / denominator);
        return -1;
    }
 
    // Driver code
    public static void Main()
    {
        int A = 1, B = 2, S = 7, N = 5;
        Console.Write(bankNotes(A, B, S, N));
    }
}
 
// This code is contributed by Akanksha Rai

<?php
// PHP implementation of the approach
 
// Function to return the amount of notes
// with value A required
function bankNotes($A, $B, $S, $N)
{
    $numerator = $S - ($B * $N);
    $denominator = $A - $B;
 
    // If possible
    if ($numerator % $denominator == 0)
        return ($numerator / $denominator);
    return -1;
}
 
// Driver code
$A = 1; $B= 2; $S = 7; $N = 5;
echo(bankNotes($A, $B, $S, $N));
 
// This code is contributed by Code_Mech
?>

<script>
 
// Javascript implementation of the approach
 
// Function to return the amount of notes
// with value A required
function bankNotes(A, B, S, N)
{
    let numerator = S - (B * N);
    let denominator = A - B;
 
    // If possible
    if (numerator % denominator == 0)
        return (Math.floor(numerator /
                           denominator));
    return -1;
}
 
// Driver Code
let A = 1, B = 2, S = 7, N = 5;
 
document.write(bankNotes(A, B, S, N) + "</br>");
 
// This code is contributed by jana_sayantan
 
</script>

3

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)