# （FB Phone）Find 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 , 0
Output: 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)

• Is it a sorted rotated array?

• @avigit no, it is not sorted

• I came up with `O(n)` solution, but the code itself is pretty ugly. I wonder if there's a more elegant solution.

``````function calculateRightCounts (diff, hash) {
hash = Object.assign({}, hash);
const n = diff.length;
const right = Array(n).fill(undefined);
right[0] = diff.filter(v => v <= 0).length;
for (let i = 1; i < n; i++) {
hash[diff[i - 1]]--;
let v = right[i - 1];
if (diff[i - 1] <= -(i - 1))
v--;
v -= hash[-(i - 1)] || 0;
right[i] = v;
}
return right;
}

function calculateLeftCounts (diff, hash) {
hash = Object.assign({}, hash);
const n = diff.length;
const left = Array(n).fill(undefined);
left[n - 1] = diff.filter(v => v <= 0).length;
for (let i = n - 2; i >= 0; i--) {
const thr = n - (i + 1);
hash[diff[i + 1]]--;
left[i] = left[i + 1] - (diff[i + 1] <= (n - i - 1) ? 1 : 0);
left[i] += hash[thr] || 0;
}
return left;
}

function findAmazingNumber (array) {

const n = array.length;
const diff = [ ...array ].map((v, i) => v - i);
const hash = {};
for (let i = 0; i < n; i++)
hash[diff[i]] = (hash[diff[i]] || 0) + 1;

const right = calculateRightCounts(diff, hash);
const left = calculateLeftCounts(diff, hash);

let max = right[0], res = 0;
for (let i = 1; i < n; i++) {
const v = right[i] + left[i - 1];
if (v > max) {
res = i; max = v;
}
}

return res;
}
``````

• This post is deleted!

• @dettier - Could you please explain the logic of your code?

• This post is deleted!

• Below is an illustration of my method, running in O(n) time.

``````#include <iostream>
#include <map>
using namespace std;
#define N 5

/* Helper Function*/
void printArrayFromPosition(int arr[N], int start){
for (size_t i = start; i < N; i++)
{
cout << arr[i] << ",";
}
for (size_t i = 0; i < start; i++)
{
cout << arr[i] << ",";
}

cout << endl;
}

/* The O(n^2) solution*/

int diffCountArray(int idx[N], int arr[N]){
int count = 0;
for (size_t i = 0; i < N; i++)
{
if (arr[i] <= idx[i])
{
count++;
}
}
return count;
}

int findANSimple(int arr[N]){
int start = 0;
int idx[N];
int maxStart = -1;
int maxCount = -1;

for (start = 0; start < N; start++)
{
//set indices according to the start position
for (int i = 0; i < N; i++)
{
idx[i] = (i - start) < 0 ? (i - start + N) : i-start; // circular mod
}

int currentCount = diffCountArray(idx, arr);
if (currentCount > maxCount){
maxStart = start;
maxCount = currentCount;
}

}

printArrayFromPosition(arr, maxStart);

return maxStart;

}

/* Below is the O(n) algorithm*/

int findANFast(int arr[N]){
int idx[N];
for (int i = 0; i < N; i++)
{
idx[i] = i;
}

int shiftRight[N]; //for each number arr[i], it needs shift at least shiftRight[i] units to the right to become an Amazing Number.
//If shiftRight[i] is negative, it means it needs to shift to the left

for (int i = 0; i < N; i++)
{
shiftRight[i] = arr[i] - idx[i];
}

int rightMost[N]; // If shift too much, a number will "pass" the end of the array and become a non-amazing number
for (int i = 0; i < N; i++)
{
rightMost[i] = N - 1 - i;
}

//Then for each arr[i], if it shifts right any units between {shiftRight[N], rightMost[i]}, it will become an Amazing Number

//count all the possible solutions
int shiftCount[N] = {0};

for (int i = 0; i < N; i++)
{
if (rightMost[i] < shiftRight[i]) // if upper bound is smaller than the lower bound, it is impossible for this number to become AN
{
continue;
}

for (int j = shiftRight[i]; j <= rightMost[i]; j++)
{
int offset = j % N;
offset = offset >= 0 ? offset : offset + N;
shiftCount[offset] ++;
}
}

//find the largest start;
int bestShift = -1;
int maxCount = -1;

for (int i = 0; i < N; i++)
{
if (shiftCount[i] >= maxCount){
bestShift = i;
maxCount = shiftCount[i]; //find the largest bestShift to the right <--> smallest possition
}

}

//value shifting right is equal to shifting indices left
return -bestShift + N  == N ? 0: -bestShift + N;

}

int main(){
//int arr[N] = { 1,5,2,4,3 };
//int arr[N] = { 1,0,0,0,0 };
//int arr[N] = { 0,1,2,3,4};
int arr[N] = { 5, 3, 8, 7, 2 };

//int start = findANSimple(arr);
int start = findANFast(arr);

cout << "start: " << start << endl;
}
``````

• say array size is n and we only rotate to right, the shift range of a number is 0 to n-1
For each number, compute the shift range so that the value is less than or equal its index.
For a number v at index i, if v<=i, shift range is [0, n-i], [n-i+v, n-1]
if v>i, range is [v-i, n-i]
So we need to determine the shift value that intersects the most number of intervals.
This is similar to meeting rooms 2.
O(nlogn)

• @bradypus its complexity is not strictly O(n), because there is a nested loop.

• python code in linear time.

``````def amazing_number(num):
k = len(num)
shift = [0] * k
for i, n in enumerate(num):
if n >= k:
continue
elif n <= 0:
shift[0] += 1
elif n > i:
shift[i + 1] += 1
if n > i + 1: shift[i + k - n + 1] -= 1
else:
shift[0] += 1
shift[i - n + 1] -= 1
if i != k - 1: shift[i + 1] += 1
total = 0
index = 0
max_number = 0
for i, s in enumerate(shift):
total += s
if total > max_number:
max_number = total
index = i
return index

num = [0, 1, 2, 3]
assert amazing_number(num) == 0

num = [1, 0, 0]
assert amazing_number(num) == 1

num = [5, 3, 8, 7, 2]
assert amazing_number(num) == 2

num = [4, 0, 1, 2, -1]
assert amazing_number(num) == 1
``````

• This post is deleted!

• @daniel.w.1

def findamazingnmber(arr):
min_index = 1000000
amazing_numbers = []
max_val = -1
for i in range(len(arr)):
if arr[i] <= i and max_val < i-arr[i]:
min_index = i
max_val = i - arr[i]
for i in range(0,min_index):
if arr[i] <= i+min_index:
amazing_numbers.append(arr[i])
for i in range(min_index,len(arr)):
if arr[i] <= i:
amazing_numbers.append(arr[i])
print "strting index is " + str(min_index)
print amazing_numbers

findamazingnmber([34,5,23,6,4,2,6,1,8,4])

• ``````
\\O(nlogn) time and O(n) space using segment trees and lazy propagation.
public int maxAmazing(int[] arr){
int[] segTree = new int[2 * arr.length - 1];
for(int i = 0; i < arr.length; i++){
int amazeIdx = i - arr[i] < 0 ? arr.length + (i - arr[i]): i - arr[i]; //Calculate the position amazeIdx such that setting the 0th index at amazeIdx or anything that is ccw to x will make this index i have an amazing number
if(amazeIdx <= i){//If amazeIdx is to the left of i
increaseInterval(segTree,0,arr.lenth - 1,0,0,amazeIdx);//the value at arr[i] will be an amazing number if indices 0 to amazeIdx are the 0th position.
}
increaseInterval(segTree,0,arr.lenth - 1, 0, i + 1, amazeIdx);//the value at arr[i] will be an amazing number if indices i + 1 to amazeIdx are the 0th position.

}
return maxValue(segTree,0);
}

private void increaseInterval(int[] segTree,int intervalStart, int intervalEnd, int idx, int amazeStart, int amazeEnd){
if(amazeStart > amazeEnd || intervalStart > amazeEnd || intervalEnd < amazeStart){
return;
}
if(intervalStart >= amazeStart && intervalEnd <= amazeEnd){
segTree[idx]++;
return;
}
int mid = intervalStart + (intervalEnd - intervalStart)/2;
increaseInterval(segTree,intervalStart,mid, (idx << 1) + 1, amazeStart,amazeEnd);
increaseInterval(segTree,mid + 1,intervalEnd,(idx << 1) + 2, amazeStart, amazeEnd);
}

private int maxValue(int[] segTree, int idx){
if(idx > segTree.length){
return 0;
}
int left = maxValue(segTree, (idx << 1) + 1);
int right = maxValue(segTree, (idx << 1) + 2);
return Math.max(left, right) + segTree[idx];
}``````

• @yu6 I think my solution is similar to your idea. I've used a segment tree.

• Summary: This problem is similar to range searching e.g. given entry and exit times of people find max number of people in a room, or given birth and death years of people, find a year in which max number of people were alive. Time complexity O(n)
Details:
First find the start and end points for each number, i.e. the range of indexes for which the number remains an amazing number. I skip the numbers greater than nums length and for each index value I start the with the next index because starting from it will indeed make the value an amazing number. while searching for range of amazing number if the index value is greater than len(nums) I break the range into two -- first one ends at len(nums)-1 and second begins from 0 till the end where the number ceases to become amazing.
Create an index array to keep a running count of maximum range overlap, iterate over intervals(ranges) and increment overlap value by 1 when see a start value and decrement for end value. Compute the running count by iterating over index list and return index corresponding to max overlap count.

``````class Interval(object):
def __init__(self, s=0, e=0):
self.start = s
self.end = e

def amazingNumber(nums):
intervals = []
for i, v in enumerate(nums):
if v > len(nums)-1: continue
start = i + 1
nextp = i+1 +len(nums)-1-nums[i]
if nextp > len(nums)-1 and start > len(nums)-1:
start = 0
end = nextp - len(nums)
interval = Interval(start, end)
intervals.append(interval)
elif nextp > len(nums)-1:
end = len(nums)-1
interval = Interval(start, end)
intervals.append(interval)
start = 0
end = nextp - len(nums)
interval = Interval(start, end)
intervals.append(interval)
else:
interval = Interval(start, nextp)
intervals.append(interval)

return findindex(intervals,len(nums))

def findindex(intervals, n):
idxlist = [0]*n
for i in intervals:
idxlist[i.start] += 1
if i.end+1 < n:
idxlist[i.end+1] -= 1
maxcnt, maxidx = 0, None
for i, v in enumerate(idxlist):
if v > maxcnt:
maxcnt = v
maxidx = i
if i+1 < n:
idxlist[i+1] += v
return maxidx

if __name__ == "__main__":
nums = [1, 0, 0] # 1
print amazingNumber(nums)
nums = [0, 1, 2, 3] # 0
print amazingNumber(nums)
nums = [5, 3, 8, 7, 2] # 2
print amazingNumber(nums)
nums = [4, 0, 1, 2, -1] #1
print amazingNumber(nums)
nums = [1, 2, 3, 4, 5, 1, 2, 9, 10, 11, 1, 2, 3, 4, 5, 6] #9
print amazingNumber(nums)
nums = [0, 0, 0, 0, 0] #0
print amazingNumber(nums)
nums = [1, 2, 3, 4, 5, 6, 7] #6
print amazingNumber(nums)
nums = [3, 5, 2, 4, 1, 0] #2
print amazingNumber(nums)
nums = [4, 0, 1, 2, -1] #2
print amazingNumber(nums)
``````

• This post is deleted!

• @dettier I don't see why you say its O(n), I think its O(n^2), since you iterate through the array once on the main function and another time (the length of the array) between leftCounts and rightCounts. So for each execution you iterate the array twice.

Am I missing something?

• Here's a simple python solution, maybe not as fast as some other ones here.

``````def find_max_amazing(nums):
size = len(nums)
# each index in results tells how many amazing
# numbers would be at each shift
results = [0]*size
for x in range(size):
if nums[x] >= 0 and nums[x] < size:
for i in range(size-x, size-x+nums[x]+1):
results[i%size] += 1
return results.index(max(results))
``````

O(n^2) worst case.

• so is this an amazing sequence [3 4 2]? 2 begins at 2 then wraps around, 3 is at 3 and 4 is at 4 if indices wrap around?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.