CODEWITHSUNDEEP
prolog
chutsu
chutsu

Reputation: 14103

How do you find missing number in list?

Say I have a List [1,2,4,5], I would like to have a predicate that returns 3 as the missing element. You can assuming that the input list is always sorted sequentially.

My solution so far:

% missing_number/2 (ListToBeChecked, ListToBeCompared, MissingNum)
missing_number([], [], []) :- !.
missing_number([Head | Tail], [Head | Rest], Number) :- 
    missing_number(Tail, Rest, Number).
missing_number(_, [X | _], [X | Node]) :- 
    missing_number(_, _, Number), !.

Upvotes: 2

Views: 732

Answers (5)

Sai C
Sai C

Reputation: 1

Please see below: The implementation is in JavaScript. But the algorithm can be converted. I hope this helps! The assumption is that the list is ascending and is an arithmetric series - n, n+1, n+2... Additionally, the list can start anywhere, not just at 0

    function getMissingNum() {
    var start = Math.floor(Math.random() * 150) / 1;
    var nElem = Math.floor(Math.random() * 20) / 1;
    var set = [];
    var rand = Math.floor(Math.random() * nElem) + start / 1;
    for (var i = start; i <= start + nElem; i++) {
        //skip one number randomly
        if (i == rand) continue;
        set.push(i);
    }

    var sum = 0;
    for (var i = 0; i < set.length; i++) {
        sum += set[i];
    }

    // SEE HERE: 
    // Total = N * (N + 1) / 2
    var max = set[set.length - 1];
    var min = set[0];// - 1;
    var actual = (((max * (max + 1)) / 2));
    var excluded = (((min * (min + 1)) / 2));
    var missing = actual - excluded - sum + start;
    if (min > start) {
        missing = missing + min;
    }
    return {
        missing: missing,
        min: min,
        max: max,
        actual: actual,
        excluded: excluded,
        rand: rand,
        start: start,
        nElem: nElem
    }
}

var results = [];
for (var i = 0; i < 100; i++) {
    var result = getMissingNum();
    if (result.rand != result.missing) {
        results.push(result);
    }
}

Upvotes: 0

black rose
black rose

Reputation: 23

it doesn't work for unsorted lists

missing([], []).
missing([H|T], R) :- missing([H|T], H, R).
missing([], _I, []).
missing([H|T], I, [I|R]) :-
    H =\= I,
    !,
    NextI is I + 1,
    missing([H|T], NextI, R).
missing([_|T], I, R) :-
    NextI is I + 1,
    missing(T, NextI, R).

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

The paradigmatic predicate append/3 many times can help in duties involving lists: here suffice to check for consecutive elements that aren't successors:

missing(L, M) :-
    append(_, [A,B|_], L),
    \+ succ(A, B), succ(A, M).

Completed

To be able to fulfill gaps of length > 1, the solution ends up almost identical to the larsman one:

missing(L, M) :-
    append(_, [A,B|_], L),
    succ(A, S), succ(P, B), between(S, P, M).

succ/2 allows a more declarative approach, but it's noticeably slower than arithmetic.

Upvotes: 3

Fred Foo
Fred Foo

Reputation: 363777

Use between/3 to generate all numbers from min to max. Use memberchk/2 (or member/2) to find the missing ones.

L = [1,2,4,5],
L = [M|_],
last(L, N),
between(M, N, I),
\+ memberchk(I, L).

Exercise for the reader: wrap this up in a predicate.

EDIT Efficient solution, by popular request:

missing([I,K|_], M) :-
    I1 is I+1,
    K1 is K-1,
    between(I1, K1, M).
missing([_|Ns], M) :-
    missing(Ns, M).

EDIT 2: More elegant version of the above, inspired by @chac, not necessarily very efficient:

missing(L,M) :- append(_, [I,J|_], L), I1 is I+1, J1 is J-1, between(I1,J1,M).

Upvotes: 4

m09
m09

Reputation: 7493

missing([], []).
missing([H|T], R) :- missing([H|T], H, R).
missing([], _I, []).
missing([H|T], I, [I|R]) :-
    H =\= I,
    !,
    NextI is I + 1,
    missing([H|T], NextI, R).
missing([_|T], I, R) :-
    NextI is I + 1,
    missing(T, NextI, R).

for the no helper predicate one.

Upvotes: 0

Related Questions