3 good answers already, but there's more!
I don't like that you modify the array you are given. This sort of thing would need to be documented, and generally creates confusion for all. You don't need arrays as inputs, so you could take IEnumerables instead without any added cost, which makes the code easier to reuse and communicates to the consumer that you aren't modifying anything. I'd consider making the parameter names a little more explicit:
public static int GetMoneySpent(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)
Your SortArrayDescending modifies the array given, and then proceeds to return it: this is how to really annoying people, because they will assume that because the method returns something that it won't be modifying the input.
You've clearly thought about edge cases, which is good. You might consider some parameter validation (e.g. checking the budget makes sense, the arrays should not be null):
if (budget < 0)
throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
if (keyboardPrices == null)
throw new ArgumentNullException(nameof(keyboardPrices));
if (drivePrices == null)
throw new ArgumentNullException(nameof(drivePrices));
At the moment the program would print -1, which is sort of makes sense, but could easily be the first clue that something has gone wrong higher-up.
As implied by J_H, you should discard before the sort. The following also clones the arrays immediately so we don't modify them:
// filter to within-budget items, sort the two arrays (ascending)
keyboards = keyboards.Where(k => k < budget).ToArray();
Array.Sort(keyboards);
drives = drives.Where(d => d < budget).ToArray();
Array.Sort(drives);
J_H has already described how you can get the optimal time complexity, but you can perform the loops at the end very simply, without needing nesting or binary search or any of that.
You also don't need to record a list of all the candidates, just keep track of the current best, as Henrik Hansen has already demonstrated:
// maximum within budget price
int max = -1;
If we start by looking at the most expensive keyboard and cheapest drive and simultaneously iterate through both, we can do this bit in linear time.
int ki = keyboards.Length - 1; // drive index
int di = 0; // drive index
while (ki >= 0 && di < drives.Length)
{
int candidate = keyboards[ki] + drives[di];
if (candidate <= budget)
{
max = Math.Max(candidate, max);
di++;
}
else
{
ki--;
}
}
Suppose we are looking at keyboard ki and drive di: candidate is the sum of their costs. If this candidate cost is no more than the budget, then it is a candidate for the max. We also know that we can check for a more pairing by looking at the next most expensive drive, di + 1. If instead the candidate was out of the budget, we know we can find a cheaper candidate by looking at the next cheapest keyboard ki - 1.
Basically, we look at each keyboard in turn, and cycle through the drives until we find the most expensive one we can get away with. When we find the first drive that is too expensive, we move onto the next keyboard. We know that we don't want any drive cheaper than the last one we looked at, because that could only produce a cheaper pair, so we can continue our search starting from the same drive.
At the end, we just return max: if we didn't find any candidates below budget, it will still be -1:
return max;
Concerning dfhwze's comment about buying more than 2 items: this process is essentially searching the Pareto front, which is done trivially and efficiently for 2 items, but becomes nightmarish for any more, so I would certainly forgive you for sticking to 2 lists ;)
The above code all in one, with added inline documentation to make the purpose explicit (useful for the consumer, so that they know exactly what it is meant to do, and useful for the maintainer, so that they also know what it is meant to do):
/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent2(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)
{
if (budget < 0)
throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
if (keyboardPrices == null)
throw new ArgumentNullException(nameof(keyboardPrices));
if (drivePrices == null)
throw new ArgumentNullException(nameof(drivePrices));
if (budget == 0)
return -1;
// filter to within-budget items, sort the two arrays (ascending)
var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
Array.Sort(keyboards);
var drives = drivePrices.Where(d => d < budget).ToArray();
Array.Sort(drives);
// maximum within budget price
int max = -1;
int ki = keyboards.Length - 1; // keyboard index
int di = 0; // drive index
while (ki >= 0 && di < drives.Length)
{
int candidate = keyboards[ki] + drives[di];
if (candidate <= budget)
{
max = Math.Max(candidate, max);
di++;
}
else
{
ki--;
}
}
return max;
}
J_H's solution (using a BinarySearch) could well be better in practise, because you only need to sort (and binary search) the shortest input: you can scan the other however you like. Implementation of that, since I too enjoy the sport:
/// <summary>
/// Returns the maximum price of any pair of a keyboard and drive that is no more than the given budget.
/// Returns -1 if no pair is within budget.
/// </summary>
/// <param name="keyboardPrices">A list of prices of keyboards.</param>
/// <param name="drivepricess">A list of prices of drives.</param>
/// <param name="budget">The maximum budget. Must be non-negative</param>
public static int GetMoneySpent3(IEnumerable<int> keyboardPrices, IEnumerable<int> drivePrices, int budget)
{
if (budget < 0)
throw new ArgumentOutOfRangeException(nameof(budget), "Budget must be non-negative");
if (keyboardPrices == null)
throw new ArgumentNullException(nameof(keyboardPrices));
if (drivePrices == null)
throw new ArgumentNullException(nameof(drivePrices));
if (budget == 0)
return -1;
// filter to within-budget items
var keyboards = keyboardPrices.Where(k => k < budget).ToArray();
var drives = drivePrices.Where(d => d < budget).ToArray();
// determine which list is shorter
IReadOnlyList<int> longList;
int[] shortList;
if (keyboards.Length < drives.Length)
{
shortList = keyboards;
longList = drives;
}
else
{
shortList = drives;
longList = keyboards;
}
// special case of empty short-list
if (shortList.Length == 0)
return -1;
// sort shortList, to facilitate binary search
Array.Sort(shortList);
// maximum within budget price
int max = -1;
foreach (var k in longList)
{
// filter faster
if (k + shortList[0] > budget)
continue;
// find most expensive drive no more than budget - k
int i = Array.BinarySearch(shortList, budget - k);
i = i >= 0
? i // found
: ~i - 1; // not found, consider next smallest
// if such a drive exists, consider it a candidate
if (i >= 0)
{
int candidate = k + shortList[i];
max = Math.Max(max, candidate);
}
}
return max;
}
