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)
      else if (score == highestValue)

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

   if (ammountOfLowestValue > 1)
      finalScore -= ((ammountOfLowestValue - 1) * lowestValue); //Same as highest
      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.

  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – vnp
    Commented Aug 25, 2014 at 22:49
  • \$\begingroup\$ 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) \$\endgroup\$
    – IEatBagels
    Commented Aug 25, 2014 at 23:05
  • \$\begingroup\$ Correct, if you can guarantee no more than the zillion runs regardless of the array size (think of multi-mega-gazillion-strong arrays). \$\endgroup\$
    – vnp
    Commented Aug 25, 2014 at 23:12
  • \$\begingroup\$ That is super interesting! But if the array had a zillion elements, I believe looping it multiple times would hurt performance \$\endgroup\$
    – IEatBagels
    Commented Aug 25, 2014 at 23:22
  • 3
    \$\begingroup\$ SE has a policy against the discussion in comments. Let's continue on chat: chat.stackexchange.com/rooms/8595/the-2nd-monitor \$\endgroup\$
    – vnp
    Commented Aug 25, 2014 at 23:26

1 Answer 1



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:


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

  • \$\begingroup\$ 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 \$\endgroup\$
    – IEatBagels
    Commented Aug 27, 2014 at 12:10
  • \$\begingroup\$ 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. \$\endgroup\$
    – Malachi
    Commented Aug 28, 2014 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.