Largest number in an array that is at least twice of others

By | May 3, 2018

Question: Given an array, there is a largest element N. Check if that number is at least twice than all the other elements in the array. Return the index if it is, else return -1

Input: {3, 6, 1, 0}

Output: -1

6 is the largest integer, and for every other number in the array x,
6 is more than twice as big as x. The index of value 6 is 1, so we return 1.

Let us try to make one more example
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 4 isn’t at least as big as twice the value of 3, so we return -1.

Algorithm:
– Scan through the array to find the unique largest element ‘N’, keeping track of it’s index maxIndex.
– Scan through the array again. If we find some x != N with N < 2 * x, we should return -1.
– Otherwise, we should return maxIndex.

 

public int twiceIndex(int[] arr) {

    int maxIndex = 0;
    for (int i = 0; i < arr.length; ++i) { if (arr[i] > arr[maxIndex])
            maxIndex = i;
    }

    for (int i = 0; i < arr.length; ++i) {
        if (maxIndex != i && arr[maxIndex] < 2 * arr[i])
            return -1;
    }
    return maxIndex;
}

Time Complexity: O(N) where N is the length of array.
Space Complexity: O(1), the space used by our int variables.

A working solution can be found here:- https://ideone.com/uyEpv9

Author: nikoo28

a tech-savvy guy and a design buff...

Enclose codes in [code lang="C"] [/code] tags