CODEWITHSUNDEEP
algorithmintegersequence
user2479920
user2479920

Reputation: 39

How to fill gaps in a sequence of integers, by choosing the best complementary sequence

Say i have this list of integers :

List A = 3 5 9 10 11 15

Say I have several other lists of integers :

List B1 = 1 2 3 4 5 6 7 8 20 25

List B2 = 4 7 8 13 17

List B3 = 10 11 12 13 14 15 16 17

NB :

Is there any algorithm that :

  1. tells if a B list fills all the gaps in the A list - or not ;
  2. (if some gaps are not filled) tells which B list fills gaps in the A list the best = highest number of gaps filled and lowest number of fat

I guess it is a classical need...

ps : i prefer .py code but pseudo-code is ok

Thanks a lot

Upvotes: 0

Views: 1781

Answers (2)

Andreas
Andreas

Reputation: 6475

I would use two iterators over the sorted arrays of A and B. The first iterates over A and the second over B. Whenever there is a gap in A the next number in B must fill it. Like this (example in C#):

var iterA = A.Sort().GetEnumerator();
var iterB = B.Sort().GetEnumerator();

iterA.MoveNext(); iterB.MoveNext();
var prevA = iterA.Current;
var curB = iterB.Current;

if (curB < prevA) return "B is fat";

while (iterA.MoveNext()) {
  var curA = iterA.Current;
  if (curA - prevA == 1) {
    prevA = curA;
    continue; // no gap
  }
  while (curA - prevA > 1) {
    if (curB != prevA + 1) return "B does not fill gap";
    if (iterB.MoveNext()) {
      curB = iterB.Current;
      prevA++;
    } else return "B does not fill gap";
  }
  prevA = curA;
}

The runtime complexity would be linear O(N) with N being the numbers between min(A) and max(A). This is just an example to give you an idea on how to approach this problem. I do not guarantee correctness of this algorithm, I have not compiled or tested it. I don't know python, but I assume that it does provide something similar to C#'s iterators.

Upvotes: 0

sp1rs
sp1rs

Reputation: 786

Following steps will do it

1) Store the gaps of A, in an array.
2) Then Map each element of A With different B(B1,B2,..)
3) And then display the result, based on the result in the above step

This is a brute force approach to solve this problem.

Upvotes: 0

Related Questions