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

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

0 comment

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; }
Code language: Java (java)

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

You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More