CODEWITHSUNDEEP
arraysalgorithmsearch
Atif
Atif

Reputation: 131

Tricky Interview question on searching

I recently heard this question from a friend who was asked this in an interview. He was not able to figure it out and i have not yet found any efficient solution to it either. I hope there is an algorithmist here who can show me a new approach

Question:

Given an array A and a number S', provide an efficient algorithm (nlogn) to find a number K such that if all elements in A greater than K are changed to K, the sum of all elements in the resulting array will be S'.

Example, given A: [90,30,100,40,20] and S' = 210, K will be 60.

Upvotes: 13

Views: 3742

Answers (6)

John Kugelman
John Kugelman

Reputation: 362087

Written in Python, which should be quite readable even if you don't know the language:

#!/usr/bin/env python

A = [90, 30, 100, 40, 20]
S = 210
K = 60

A    = sorted(A)
prev = 0
sum  = 0

for index, value in enumerate(A):
    # What do we need to set all subsequent values to to get the desired sum?
    solution = (S - sum) / (len(A) - index)

    # That answer can't be too big or too small.
    if prev < solution <= value:
        print solution

    sum += value
    prev = value

Result:

60

Sorting is O(n log n) and the loop is O(n). Combined the algorithm as a whole is therefore O(n log n).

Upvotes: 15

murasing
murasing

Reputation: 412

Well it looks like I am late but anyway hope this algorithm makes some sense .

  1. First divide S with the array size . You will get 42 .
  2. Find how many numbers in the array are greater than 42 , here it is 2 (P) .
  3. Add all the numbers less than 42 and find N = 210 - (sum of numbers less than 42) .

  4. In the end N/P should give you the perfect answer and it's in O(N) Time complexity and O(1) Space Complexity.

    Find the executing code here : http://ideone.com/MDL3iy

    import java.util.Scanner;
class Ideone {

public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int S = in.nextInt();
int[] array = {90,30,100,40,20};
int len = array.length;
int sAvg = S/len;

int trackSmallerThanAverage = 0;
int countMorethanAverage = 0;

for(int i=0; i<len; i++) {
    if(array[i] > sAvg) {
        countMorethanAverage ++;
    } else if (array[i]<sAvg) {
        trackSmallerThanAverage += array[i];
        }

    }

    int finalValue = ( S - trackSmallerThanAverage )/countMorethanAverage;
    System.out.println(finalValue);
    in.close();

}
}

Upvotes: 2

banjara
banjara

Reputation: 3890

sort it nlogn

int[] sortedArray;
int s;

int sum=0;

for(int i=0; i<sortedArray.length; i++){
  sum = sum + sortedArray[i];

  if((s - sum)/(sortedArray.length - i) < sortedArray[i+1]){
    return (s - sum)/(sortedArray.length - i);
  }
}

Upvotes: 0

jonderry
jonderry

Reputation: 23643

This can be accomplished without sorting in O(n) time by using a variation on linear time select as follows (note that the running times of the iterations of the while loop form a geometric series -- the partition subroutine splits a range of an array, from lower to upper, into elements less than or greater than the element of rank mid, and the running time is proportional to the size of the range of the array):

foo(x, s) {
  sumBelow = 0;
  lower = 0;
  upper = x.size();
  while (lower + 1 != upper) {
    mid = (upper + lower) / 2;
    partition(x, lower, mid, upper); // O(upper - lower) time
    sumb = 0;
    maxb = 0; // assuming non-negative to avoid use of flags
    for (i = lower; i < mid; i++) {
      sumb += x[i];
      maxb = max(maxb, x[i]);
    }
    if (sumBelow + sumb + maxb * (x.size() - mid) <= s) {
      lower = mid;
      sumBelow += sumb;
    } else {
      upper = mid;
    }
  }
  K = (s - sumBelow) / (x.size() - lower);
  if (K > maxElement(x)) return error();
  else return K;
}

Upvotes: 5

MAK
MAK

Reputation: 26586

Here's my solution. I am basically doing a binary search for the value of K in the range [0, max(A)]. While this avoids having to sort the array first (thus preserving the original array), it is still O(n*log(k)) where n is the number of elements in A and k is the maximum value in A.

#! /usr/bin/env python
from itertools import imap

def findK(A,S):
    lo,hi=0,max(A)
    while lo<hi:
        mid=(hi+lo+1)>>1
        result=sum(imap(lambda x: x if x<mid else mid,A))
        if result<=S:
            lo=mid
        else:
            hi=mid-1
    return lo

if __name__=='__main__':
    print findK(A=[90,30,100,40,20],S = 210)

Upvotes: 1

Nick Alger
Nick Alger

Reputation: 1104

First sort the list smallest to largest and find how long it is. Then start adding up the numbers one by one. At each step, also find a lower limit on what the sum could be - what the sum of the whole list would be, if all of the rest of the numbers you haven't added in yet are the same as the current number.

At some point this lower limit on the sum will go from being smaller than S', to larger than S', and at that point you can do some arithmetic to determine what the cutoff should be. eg (C = current sum, L = lower limit on total sum):

start
[90 30 100 40 20]
sort
[20 30 40 90 100]
start adding up the sum
C1 = 20
L1 = 20 + 4*20 = 100 < 210

C2 = 20 + 30 = 50
L2 = 50 + 3*30 = 140 < 210

C3 = 50 + 40 = 90
L3 = 90 + 2*40 = 170 < 210

C4 = 90 + 90 = 180
L4 = 180 + 1*90 = 270 > 210 //too big!

S' = C3 + K*2
therefore
K = (S'-C3)/2 = 60

Upvotes: 6

Related Questions