Submission 9d92db7e...

ChallengeRemove duplicate elements
Submitter0x888888417655103...
Submitted at2018-40-29
Gas used405373
pragma solidity 0.4.24;

contract Unique {

    function uniquify(
        uint[] input
    ) public pure returns(uint[] ret) {
        uint inLen = input.length;
        if (inLen < 2) {
            return input;
        }
        uint outLen;
        if (inLen <= 64) {
            outLen = uniquifyLess(input, inLen);
        } else {
            outLen = uniquifyMore(input, inLen);
        }
        if (inLen == outLen) {
            return input;
        }
        uint[] memory output = new uint[](outLen);
        for (uint j = 0; j < outLen; j++) {
            output[j] = input[j];
        }
        return output;
    }

    function uniquifyLess(
        uint[] input,
        uint inLen
    ) private pure returns(uint outLen) {
        uint y;
        uint filter;
        for (uint i = 0; i < inLen; i++) {
            y = (1 << input[i] % 241) & (1 << input[i] % 151);
            if (filter & y == 0) {
                filter = filter | y;
                input[outLen++] = input[i];
            }
        }
        return outLen;
    }

    function uniquifyMore(
        uint[] input,
        uint inLen
    ) private pure returns(uint outLen) {
        uint h;
        uint magic = inLen * 4 - 1;
        uint[] memory filter = new uint[] (magic+1);
        for (uint i = 0; i < inLen; i++) {
            h = input[i] % magic;
            if (filter[h] == 0) {
                filter[h] = 1;
                input[outLen++] = input[i];
            }
        }
        return outLen;
    }
}