The Fake Geek's blog: Amazing number
Brutal force is trivial: For each index as starting point, count number of amazing number in the array, then update index if we see a max.
There is a clever way of doing it in the original post, which utilizes interval. For any number, if it's larger than the length of the array, there is no way we can make it an amazing number. Otherwise, starting from the next index of the current one can always make the number an amazing number. The largest index would be length_of_array + current_index - array[current_index]. This is because current_index - array[current_index] is the index we need to make the number an amazing number. If the number is larger than current index, this index will become negative, so we need to add length of array to keep the index in the array. For current_index > array[current_index], this operation will lead to index > length of array, so we mod the index by length.
After we get all intervals, we need to find the index that all intervals intersects most, which is the index that contains the most amazing numbers. To do that, we can use algorithm in Range Addition.
Read full article from The Fake Geek's blog: Amazing number
Define amazing number as: its value is less than or equal to its index. Given a circular array, find the starting position, such that the total number of amazing numbers in the array is maximized.Example 1: 0, 1, 2, 3 Ouptut: 0. When starting point at position 0,all the elements in the array are equal to its index.So all the numbers are amazing number.Example 2: 1, 0 , 0Output: 1. When starting point at position 1,the array becomes 0, 0, 1. All the elements are amazing number.If there are multiple positions, return the smallest one.should get a solution with time complexity less than O(N^2)
Brutal force is trivial: For each index as starting point, count number of amazing number in the array, then update index if we see a max.
There is a clever way of doing it in the original post, which utilizes interval. For any number, if it's larger than the length of the array, there is no way we can make it an amazing number. Otherwise, starting from the next index of the current one can always make the number an amazing number. The largest index would be length_of_array + current_index - array[current_index]. This is because current_index - array[current_index] is the index we need to make the number an amazing number. If the number is larger than current index, this index will become negative, so we need to add length of array to keep the index in the array. For current_index > array[current_index], this operation will lead to index > length of array, so we mod the index by length.
After we get all intervals, we need to find the index that all intervals intersects most, which is the index that contains the most amazing numbers. To do that, we can use algorithm in Range Addition.
public int getAmazingNumber(int[] array) { List<Interval> startIndexInterval = new ArrayList<>(); int len = array.length; for (int i = 0; i < len; i++) { if (array[i] >= len) { continue; } // for i = len - 1, next interval int start = (i + 1) % len; // for array[i] < i, mod to make sure index is in the array //which may lead start > end int end = (i - array[i] + len) % len; startIndexInterval.add(new Interval(start, end)); } int[] indexCount = new int[len]; for (Interval interval : startIndexInterval) { indexCount[interval.start]++; //for start > end, we need to split interval to two //[start, len - 1], [0, end] if (interval.start > interval.end) { indexCount[0]++; } if (interval.end + 1 < len) { indexCount[interval.end + 1]--; } } int max = indexCount[0]; int rstIndex = 0; for (int i = 1; i < len; i++) { indexCount[i] += indexCount[i - 1]; if (indexCount[i] > max) { rstIndex = i; max = indexCount[i]; } } return rstIndex; }