# Summing up distinct elements in steps (follow up)

This is a "follow up" to an answer I gave on this question : Summing up distinct elements in steps

Here are the OP's requirements :

"My current task is to find a score from an array where the highest/lowest scores have been taken away, and if the highest/lowest occur more than once (ONLY if they occur more than once), one of them can be added:

E.g. int[] scores = [4, 8, 6, 4, 8, 5] therefore the final addition will be ∑4,8,6,5=23.

Another condition of the task is that LINQ cannot be used, as well as any of the System.Array methods (you can see by my previously ask questions that has been a bit of a pain for me, since I solved this with LINQ in less than 5 minutes)."

public int CalculateScore(int[] scores)
{
int lowestValue = int.MaxValue,
highestValue = int.MinValue,
ammountOfHighestValue = 1,
ammountOfLowestValue = 1,
finalScore = 0;

foreach (int score in scores)
{
finalScore += score;

if (score < lowestValue)
{
lowestValue = score;
ammountOfLowestValue = 1; //We need to reset the ammount
}
else if (score > highestValue)
{
highestValue = score;
ammountOfHighestValue = 1; //We need to reset the ammount
}
else if (score == lowestValue)
ammountOfLowestValue++;
else if (score == highestValue)
ammountOfHighestValue++;
}

if (ammountOfHighestValue > 1)
//This way, we keep the highest score once.
finalScore -= ((ammountOfHighestValue - 1) * highestValue);
else
finalScore -= highestValue; //The value is there once, we remove it.

if (ammountOfLowestValue > 1)
finalScore -= ((ammountOfLowestValue - 1) * lowestValue); //Same as highest
else
finalScore -= lowestValue;

return finalScore;
}


I'm interested about how can I remove the multiple if/else statements while keeping a complexity of O(n) and still loop through the array only once.

• It is important to realize that a complexity of going over an array multiple times is still $O(n)$, as long as the number of passes is fixed (that is, doesn't depend on $n$). The performance difference between doing everything in one pass, or splitting job between dedicating passes is not measurable. – vnp Aug 25 '14 at 22:49
• Oh I didn't know about that, I'm just starting to learn big O notation. You mean, if I run trough the array a zillion times, notation is still O(n) right? (Just want to make sure, non-native english here) – IEatBagels Aug 25 '14 at 23:05
• Correct, if you can guarantee no more than the zillion runs regardless of the array size (think of multi-mega-gazillion-strong arrays). – vnp Aug 25 '14 at 23:12
• That is super interesting! But if the array had a zillion elements, I believe looping it multiple times would hurt performance – IEatBagels Aug 25 '14 at 23:22
• SE has a policy against the discussion in comments. Let's continue on chat: chat.stackexchange.com/rooms/8595/the-2nd-monitor – vnp Aug 25 '14 at 23:26

Bugs

Console.WriteLine(CalculateScore(new[] { 1 } ));
Console.WriteLine(CalculateScore(new[] { 2, 1 } ));
Console.WriteLine(CalculateScore(new[] { 3, 2, 1 } ));


What's the expected output? The question is maybe underspecified for the first case (I would say it's 0), but the other two are clear: 0 and 2.

But we get:

-2147483648
-2147483646
-2147483643


Bonus question: what is the correct result for the array { 1, 1 }? I would say 2, but your program returns 0.

• You are right, the OP didn't specify any criteria for these cases so I didn't think about them, but obviously my program is flawed – IEatBagels Aug 27 '14 at 12:10
• the output for the input {1, 1} should be 1 because there are two instances of the lowest number and two instances of the highest number. – Malachi Aug 28 '14 at 18:33