(FB Phone)Find Amazing Number


  • 4
    D

    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)


  • 0
    A

    Is it a sorted rotated array?


  • 0
    D

    @avigit no, it is not sorted


  • 2

    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;
    }
    

  • 0
    B
    This post is deleted!

  • 0
    B

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


  • 0
    B
    This post is deleted!

  • 6
    B

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

    #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;
    }
    

  • 2

    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)


  • 0

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


  • 0
    A

    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
    

  • 0
    S

    Can you please explain the logic too ? Not following what is happening here:
    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


Log in to reply