Is there a way to make the Loop Code make it faster?

Question

For Loop Code

 int counts = 0;
            List<int> count = new List<int>();
            List<int> goodnumber = new List<int>();
            for (int i = lower; i <= upper; i++)
            {
                if (!badNumbers.Contains(i)) {
                        goodnumber.Add(i);
                } else {
                    count.Add(goodnumber.Count);
                    goodnumber = new List<int>();
                } 
                if (i == upper) {
                    count.Add(goodnumber.Count);
                    counts = count.Max();
                }
            }
            return counts;

is there a way to optimize my code above? because the running time for the code above is exceeding in 3 secs. how can I make it 2 or below?

Answer 1

Here is a general solution:

using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var lower = 1;
            var upper = 10;
            var elementCount = upper - lower + 1;
            var numbers = Enumerable.Range(1, elementCount);
            var badNumbers = new HashSet<int> { 5, 4, 2, 15 };
            var maxCount = CalculateCounts(numbers, badNumbers).Max();
        }

        private static IEnumerable<int> CalculateCounts<T>(IEnumerable<T> items, ISet<T> splitOn)
        {
            var count = 0;

            foreach (var item in items)
            {
                if (!splitOn.Contains(item)) count++;
                else
                {
                    yield return count;
                    count = 0;
                }
            }

            yield return count;
        }
    }
}

Answer 2

The correct way to "optimize" your code is to rewrite it. You need to think differently. The problem you have has various different solutions and you are complicating it too much.

You don't need to process the input in one long cycle only. You can pre-process the list somehow, in a way, that would help you. For example sort it.

Another thing that could help you is to have a variable (or variables) in which you are storing some intermediate result. For example running max, min, sum, or previous value of something

Think about how you could solve the problem mathematically. Isn't it just the difference of numbers you are trying to find?

You could sort the list, calculate the difference between each element, bound it by your lower and upper borders. You can either update the running maximum difference during the loop or find the maximum difference from the list of differences.

Answer 3

1. Call List.Clear() instead of creating new List inside the loop

2. Call count.Max() outside the loop

3. Remove the last if and add this line after the loop count.Add(goodnumber.Count)

       int counts = 0;
       List<int> count = new List<int>();
       List<int> goodnumber = new List<int>();
       for (int i = lower; i <= upper; i++)
       {
           if (!badNumbers.Contains(i)) {
                   goodnumber.Add(i);
           } else {
               count.Add(goodnumber.Count);
               goodnumber.Clear();
           } 
   
       }
   
       count.Add(goodnumber.Count);
       counts = count.Max();
       return counts;
   

BTW, I don't know what are you trying to achieve with this code.

Answer 4

There's a few improvements you can make.

1. badNumbers should probably be a HashSet<int> which will provide you close to O(1) lookup.
2. You don't actually care about storing the "good numbers" (you don't use that data), so it would be more efficient to just store how many good numbers you encounter.
3. Now you just want the max streak size (i.e. max number of consecutive good numbers) you encounter, and you can use Math.Max to compare the last "good" count with the current "good" count and choose the largest.

The code looks like this:

HashSet<int> badNumbers = new HashSet<int>() { 5, 4, 2, 15 };
int counts = 0;
int goodNumberCount = 0;
for (int i = lower; i <= upper; i++)
{
    if (!badNumbers.Contains(i)) {
        ++goodNumberCount;
    } else {
        counts = Math.Max(counts, goodNumberCount);
        goodNumberCount = 0;
    }
}
counts = Math.Max(counts, goodNumberCount); 
return counts;