Submission 063585fb...

Challenge	Remove duplicate elements
Submitter	0xabcdef0db461f2f...
Submitted at	2018-02-29
Gas used	582655

/**
 * 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[]) {
        if (input.length < 2) {
            return input;
        } else if (input.length == 2) {
            if (input[0] != input[1]) {
                return input;
            } else {
                uint[] memory ret = new uint[](1);
                ret[0] = input[0];
                return ret;
            }
        } else {
            return uniquify_more(input, input.length / 8);
        }
    }

    function uniquify_more(uint[] input, uint size) internal pure returns(uint[]) {
        uint[] memory filter = new uint[] (size);
        uint bits = size * 256 - 1;
        uint cnt = 0;
        uint idx;
        uint h;
        uint x;
        uint y;
        for (idx = 0; idx < input.length; idx++) {
            h = input[idx] % bits;
            x = h / 256;
            y = (1 << (h % 256));
            if (filter[x] & y == 0) {
                filter[x] = filter[x] | y;
                input[cnt] = input[idx];
                cnt += 1;
            }
        }
        uint[] memory ret = new uint[](cnt);
        for (idx = 0; idx < cnt; idx++) {
            ret[idx] = input[idx];
        }
        return ret;
    }
}