Find a number in an array that is twice as big as any other in linear time

user_5540416 0
Viewed 125

I have been tasked to improve my algorithm that finds a number that is twice as big as any other number in an array. It currently runs in O(n^2) and i need to make it run in O(n).

func twiceAsOldExact(p []person) bool {
for i := 0; i < len(p); i++ {
    for j := 0; j < len(p); j++ {
        if j == i {
            continue
        }
        if p[i].age == 2*p[j].age {
            return true
        }
    }
}
return false
}

I have thought about sorting the array using Counting Sort and work from there, however i am not sure if that will work.

Say that i have this array a := []int{4,5,12,24}

The algorithm should return true because 24 is twice as big as 12.

If the array was a := []int{4,8,10,16}

It would return true either because of 8 that is twice as big as 4, or 16 that is twice as big as 8, depending what completes the check first.

Do any of you have any pointers on how should i tackle this problem? Partial solution is fine, or just advice, since it's for an interview perhaps it's not moral to ask for outside help (although that's what i would do in work).

Best regards!

Proposed Solution

func twiceAsOldExact2(p []person) bool {
    m := make(map[int]int)
    for i := 0; i < len(p); i++ {
        m[p[i].age] = i
    }

    for i := 0; i < len(p); i++ {
        if _, ok := m[2*p[i].age]; ok {
            return true
        }
    }
    return false
}
go big-o sorting algorithm
2 Answers

Put values into map, and for every value x check whether 2*x presents in the map.

Inserting into a map (implemented as hashtable) and searching takes in average O(1) per operation, so map approach is close to linear O(n) and it is much faster than quadratic O(n^2) two-loops one (but uses memory)

user_8444160

Copy your array into hash table, thereafter search for 2x in that hashtable. All is O(N), since N elements, and hash table insert and search is O(1).

user_3399370
Related