(FB Phone)Find Amazing Number


  • 6
    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!

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

  • 3

    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)


  • 1

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


  • 1
    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
    This post is deleted!

  • -1
    P

    @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])


  • -1
    
    \\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];
    }

  • 0

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


  • 0
    B

    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)
    

  • 0
    L
    This post is deleted!

Log in to reply
 

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