Groovy web console

subscribe to the feed Subscribe
to this
site

check for dups in array

Published 1 decade ago by mike
Actions Execute script  ▶ Edit in console Back to console Show/hide line numbers View recent scripts
// check if an list of n integers inclusive between 1 and n has a duplicate

def hasDup(list) {
    def i=0, hasDup = false
    list.each { item ->
        def key = Math.abs(item) - 1
        def value = list[ key ]
        list[ key ] = -value             //mark item as visited by making negative               
    }
    list.eachWithIndex{ item, pos ->
        if(item > 0)
            hasDup = true                //thus item as current position was not visited
        list[pos] = Math.abs(item)       //restor the value to it's original positive value
    }
    return hasDup
}

assert hasDup([1,2,3,4,5,5])         == true
assert hasDup([1,2,3,4,5])           == false
assert hasDup([1,2,2,3,4,5])         == true
assert hasDup([1,2,2,3,3,5])         == true
assert hasDup([1,1,3,3,5,5])         == true
assert hasDup([5,5,3,3,1,1])         == true
assert hasDup([2,4,3,3,1,2])         == true
assert hasDup([5,1,1,5,2,5])         == true
assert hasDup([1,6,1,6,1,6])         == true
assert hasDup([1,6,1,6,1,6,6,2])     == true
assert hasDup([1,6,1,6,1,6,6,6,1,2]) == true
assert hasDup([5,1,4,2,3,7,6])       == false
assert hasDup([4,3,2,1])             == false
println "all assertions valid"