How to solve this interview problem.

Revision en7, by 444iq, 2019-11-03 18:15:42

You are given an array of N integers where N <= 10^5 and arr[i] >= 1 and arr[i] <= 10^6. Each time you find the sum of all the elements in the array, divide it by 2 and take the floor value. The number which is closest to this value is removed from the array, in case of tie the number with lowest id is removed. The process continues until there is single element in the array. Find the single element. The array can have duplicates.

How to solve this problem in the given time constraints. Brute force will be O(n^2)

Example :

N = 4 arr[] = 1 3 5 7

Output = 5

in first step, sum = 16, its half = 8, closest to it = 7, remove 7, now the array is 1 3 5

in second step, sum = 9, its half = 4, closest to it is 3 and 5, 3 is with lowest id, remove it, now array is 1 5

in second step, sum = 6, its half = 3, remove 1. final array is 5.

There were 3 problems, one was valid bracket sequence, other was in out dp but n was 1000 so it can be solved with normal dfs too in N^2. this was the last problem

#### History

Revisions Rev. Lang. By When Δ Comment
en7 444iq 2019-11-03 18:15:42 62
en6 444iq 2019-11-03 18:14:10 1 Tiny change: 'nOutput = \n\nin fir' -> 'nOutput = 5\n\nin fir'
en5 444iq 2019-11-03 18:13:54 2 Tiny change: ' array is 7. \n\nTher' -> ' array is 5. \n\nTher'
en4 444iq 2019-11-03 18:13:37 1 Tiny change: 'nOutput = 7\n\nin fir' -> 'nOutput = \n\nin fir'
en3 444iq 2019-11-03 18:07:22 105
en2 444iq 2019-11-03 18:06:32 5
en1 444iq 2019-11-03 18:05:58 899 Initial revision (published)