Submission 9fa7ab11...

ChallengeRemove duplicate elements
Submitterhyszeth.eth
Submitted at2018-55-26
Gas used5191978
/**
 * 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) {
        if(input.length == 0) return;
        uint i;
        uint j;
        uint len = input.length;
        uint candidate; // candidate uint to be added to <ret>
        uint uniqueIndex = 0; // index of unique list (offset into <input>)
        // Strategy is to build a unique list over top of <input>
        // The <uniqueIndex> keeps track of the end of the unique list.
        for(i = 0; i < len; ++i) {
            candidate = input[i];
            for(j = 0; j <= uniqueIndex; ++j) {
                if(input[j] == candidate) break;
            }
            if(j == uniqueIndex+1) {
                ++uniqueIndex;
                // keep candidate
                if(uniqueIndex != i) input[uniqueIndex] = candidate;
            }
        }
        // Construct <ret> out of unique subset of <input>
        // if input was not unique
        if(uniqueIndex + 1 < len) {
            ret = new uint[](uniqueIndex+1);
            for(i = 0; i <= uniqueIndex; ++i) ret[i] = input[i];
            return ret;
        }
        // input was already unique
        ret = input;
    }
}