Submission c55b63cd...

Challenge	Remove duplicate elements
Submitter	0xabcdef0db461f2f...
Submitted at	2018-08-02
Gas used	516716

/**
 * This file is part of the 1st Solidity Gas Golfing Contest.
 *
 * This work is licensed under Creative Commons Attribution ShareAlike 3.0.
 * https://creativecommons.org/licenses/by-sa/3.0/
 */

pragma solidity 0.4.24;

contract Unique {
    /**
     * @dev Removes all but the first occurrence of each element from a list of
     *      integers, preserving the order of original elements, and returns the list.
     *
     * The input list may be of any length.
     *
     * @param input The list of integers to uniquify.
     * @return The input list, with any duplicate elements removed.
     */
    function uniquify(uint[] input) public pure returns(uint[] ret) {
        uint inLen = input.length;
        uint outLen;
        if (inLen < 2) {
            return input;
        } else if (inLen == 2) {
            outLen = input[0] == input[1] ? 1 : 2;
        } else if (inLen <= 32) {
            outLen = uniquifyFew(input);
        } else {
            outLen = uniquifyMuch(input, inLen / 8);
        }
        if (inLen == outLen) {
            return input;
        }
        else {
            assembly {
                mstore(sub(input, 0x20), 0x20)
                mstore(input, outLen)
                return(sub(input, 0x20), add(mul(0x20, outLen), 0x40))
            }
        }
    }

    function uniquifyFew(uint[] input) internal pure returns(uint) {
        uint filter;
        uint outLen;
        for (uint i = 0; i < input.length; i++) {
            uint h = input[i] % 255;
            uint y = (1 << h);
            if (filter & y == 0) {
                filter = filter | y;
                input[outLen] = input[i];
                outLen += 1;
            }
        }
        return outLen;
    }

    function uniquifyMuch(uint[] input, uint filterSize) internal pure returns(uint) {
        uint[] memory filter = new uint[] (filterSize);
        uint outLen;
        uint magic = filterSize * 256 - 1;
        for (uint i = 0; i < input.length; i++) {
            uint h = input[i] % magic;
            uint x = h / 256;
            uint y = (1 << (h % 256));
            if (filter[x] & y == 0) {
                filter[x] = filter[x] | y;
                input[outLen] = input[i];
                outLen += 1;
            }
        }
        return outLen;
    }
}