How to solve this interview problem.

Правка en5, от 444iq, 2019-11-03 18:13:54

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 =

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. this was the last problem

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)