How to calculate larger gap in array of Biginteger in C#?-CodePudding

I got an array of random BigIntegers. Ie:

BigInteger[] series = new BigInteger[6];
series[0]=1000;
series[1]=2000;
series[2]=4000;
series[3]=1000;
series[4]=5000;
series[5]=6000;

I want to find the largest gap(Ie:the larger gap is between 2001 and 3999) and return the two boundary values.

I want to know what numbers do not exist between the smallest and the largest number?

Anybody got an idea?

CodePudding user response：

In case the question was to find the biggest Gap between any 2 items of the array, and not necessarily 2 successive one, then you just have to sort it first. And as you know it is sorted, the remaining operations are simplified.

using System.Numerics;
using System.Linq;

public static class BigIntHelper
{
  // find the biggest gap between any 2 elements
  public static (BigInteger start, BigInteger end) GetBiggestGap(BigInteger[] data)
  {
    BigInteger last = 0, start = 0, end = 0, delta = -1;
    foreach(var bi in data.OrderBy(bi => bi))
    {
      if (delta < 0)
        start = end = bi;
      else
        if (bi - last > delta)
        {
          start = last;
          end = bi;
          delta = end - start;
        }
      last = bi;
    }
    return (start, end);
  }
}

static class Program
{
  static int Main()
  {
    BigInteger[] series = new BigInteger[6] { 1000, 2000, 4000, 1000, 5000, 6000 };
    var result = BigIntHelper.GetBiggestGap(series);
    Console.WriteLine($"The largest gap is between {result.start} and {result.end}");
    return 0;
  }
}

CodePudding user response：

You can just write a cycle which checks the gap and store the starting and ending indicies

using System.Linq;
using System.Numerics;

static class Program
{
    static BigInteger abs(BigInteger i)
    { 
        return i > 0 ? i : -i;
    }
    static int Main()
    {
        BigInteger[] series = new BigInteger[6];
        series[0] = 1000;
        series[1] = 2000;
        series[2] = 4000;
        series[3] = 1000;
        series[4] = 5000;
        series[5] = 6000;

        int idx1 = -1, idx2 = -1;
        BigInteger maxGap = 0;

        for (int i = 0; i < 6 - 1; i  )
        {
            if (abs(series[i] - series[i   1]) > maxGap)
            {
                maxGap = abs(series[i] - series[i   1]);
                idx1 = i;
                idx2 = i   1;
            }
        }

        if (idx1 >= 0 && idx2 >= 0)
        {
            Console.WriteLine($"The largest gap is between {idx1} and {idx2}");
            if (series[idx1] > series[idx2])
            {
                int swap = idx2;
                idx2 = idx1;
                idx1 = swap;
            }

            Console.WriteLine($"Missing values between {series[idx1]} and {series[idx2]}");
            for (BigInteger i = series[idx1]   1; i < series[idx2]; i  )
            {
                Console.WriteLine(i);
            }
        }

        return 0;
    }
}

CodePudding user response：

In this code, BigIntHelper.GetBiggestGap will do the trick.

    
public static class BigIntHelper
{
    public static class BigIntHelper
    {
      public static (BigInteger start, BigInteger end) GetBiggestGap(BigInteger[] data)
      {
        BigInteger start = 0, end = 0, delta = -1;
        for (int i = 0; i < data.Length - 1; i  )
        {
          if (BigInteger.Abs(data[i] - data[i   1]) > delta)
          {
            start = BigInteger.Min(data[i], data[i   1]);
            end = BigInteger.Max(data[i], data[i   1]);
            delta = end - start;
          }
        }
        return (start, end);
      }
    }
}
    
static class Program
{
    static int Main()
    {
      BigInteger[] series = new BigInteger[6] { 1000, 2000, 4000, 1000, 5000, 6000 };
      var result = BigIntHelper.GetBiggestGap(series);
      Console.WriteLine($"The largest gap is between {result.start} and {result.end}");
      return 0;
    }
}