How to solve this interview problem.

Revision en6, by 444iq, 2019-11-03 18:14:10

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

History

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