6
\$\begingroup\$

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.

\$\endgroup\$
  • 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 Aug 25 '14 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 Aug 25 '14 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 Aug 25 '14 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 Aug 25 '14 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 Aug 25 '14 at 23:26
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\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 Aug 27 '14 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 Aug 28 '14 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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