Array Of Integers

August 28, 2018

Our solution takes time O(n). First we calculate the minimum and maximum elements of the array; each calculation takes O(n). Then we scan the array from left to right, counting the number of integers less than half the maximum in one counter, and the number of integers greater than twice the minimum in the other counter, finally returning the minimum of the two counts:

(define (f xs)
  (let ((mn (* (apply min xs) 2)) (mx (/ (apply max xs) 2)))
    (let loop ((xs xs) (lo 0) (hi 0))
      (cond ((null? xs) (min lo hi))
            ((< (car xs) mn) (loop (cdr xs) (+ lo 1) hi))
            ((< mx (car xs)) (loop (cdr xs) lo (+ hi 1)))
            (else (loop (cdr xs) lo hi))))))

If you’re clever about computing the minimum and maximum, you can make the entire calculation in two linear-time passes. Here’s the example:

> (f '(4 5 3 8 3 7))
2

You can run the program at https://ideone.com/sxBScO.

Advertisements

Pages: 1 2

16 Responses to “Array Of Integers”

  1. Rutger said

    In Python, a rather inefficient solution (2^n). For each subset of the list, determine whether it satisfies the constraint. @Programmingpraxis: i don’t believe your code handles [1,5,5,20] correctly.

    from itertools import chain, combinations
    
    def valid_subset(s):
    	result = []
    	for combination in chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1)):
    		if min(combination) *2 >= max(combination):
    			result.append(combination)
    	return result
    
    testcases = [
    		[4,5,3,8,3,7],
    		[1,5,5,20],
    		[1, 2],
    		[4],
    		[]
    	]
    
    for l in testcases:
    	vs = valid_subset(l)
    	if vs:
    		solution = sorted(vs, key=len)[-1]
    		print(l, "solved by removing", len(l) - len(solution), "item(s), example result", solution)
    	else:
    		print(l, "has no solution")
    
    # outputs:
    # [4, 5, 3, 8, 3, 7] solved by removing 2 item(s), example result (4, 5, 8, 7)
    # [1, 5, 5, 20] solved by removing 2 item(s), example result (5, 5)
    # [1, 2] solved by removing 0 item(s), example result (1, 2)
    # [4] solved by removing 0 item(s), example result (4,)
    # [] has no solution
    
  2. Steve said

    Klong version – Uses same logic as @ProgrammingPraxis, except:
    If the counts of lesser and greater numbers are equal and are greater than half the length of the list, then return counts plus the result of e2(new list composed of the original list without the lesser and greater numbers).

    
            e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]}
            e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<n2; n1:| n2<n1; n2:| n1<len%2; n1; e2((2*(len-n1))+(-len-n1)_(len-n2)_l2)]}
    
    

    Examples:

        {.w(x); .p(" --> ",,/:~e(x))}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [4 5 3 8 3 7]];"done"
    

    [] –> No solution
    [4][ –> 0]
    [2 2][ –> 0]
    [1 3 5][ –> 1]
    [1 5 5 20][ –> 0]
    [4 5 3 8 3 7][ –> 2]
    “done”

  3. Klong version 2 (Version 1 was wrong)

            e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]}
            e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<n2; n1:| n2<n1; n2:| n1<len%2; n1; e2((-len-n1)_(len-n2)_l2)+(2*(len-n1))]}
    

    Examples:
    {.w(x); .p(” –> “,,/:~e(x))}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [4 5 3 8 3 7]];”done”
    [] –> No solution
    [4][ –> 0]
    [2 2][ –> 0]
    [1 3 5][ –> 1]
    [1 5 5 20][ –> 2]
    [4 5 3 8 3 7][ –> 2]
    “done”

  4. Daniel said

    Although it’s not explicitly stated in the problem, I interpret that the goal is to find the minimum number of elements that can be removed to satisfy the condition. Otherwise, the solution could always be to remove all but one element.

    @bookofstevegraham, I’m not familiar with klong, but it sounds like your algorithm may not handle the case where the number of high elements that needs to be dropped differs from the number of low elements to drop. For example, what does your algorithm return for [1, 2, 20, 21, 22, 200]? Under the interpretation of the question I gave in my last paragraph, the expected answer would be 3 (remove elements 1, 2, and 200).

    Here’s an O(n log n) solution in C. It sorts the list and finds the longest contiguous valid group.

    #include <stdio.h>
    #include <stdlib.h>
    
    int compar(const void* a, const void* b) {
        int x = *(int*)a;
        int y = *(int*)b;
        return (x < y) ? -1 : (x > y);
    }
    
    int drop_count(int* array, int n) {
        int result = n - 1;
        qsort(array, n, sizeof(int), compar);
        int j = 0;
        for (int i = 0; i < n; ++i) {
            int lower = array[i];
            while (j+1 < n && array[j+1] <= 2 * lower) ++j;
            int tmp = n - j + i - 1;
            if (tmp < result) result = tmp;
        }
        return result;
    }
    
    int main(int argc, char* argv[]) {
        int array[argc - 1];
        for (int i = 1; i < argc; ++i) {
            array[i-1] = atoi(argv[i]);
        }
        int result = drop_count(array, argc - 1);
        printf("%d\n", result);
        return EXIT_SUCCESS;
    }
    

    Example:

    $ ./drop_count 1, 2, 20, 21, 22, 200
    3
    
  5. Me said

    As I am a beginner, this is my simple code, If any body wants to give feed back it is acceptable.

    a = [4,5,3,8,3,7]
    count1, count2 = 0, 0
    maxi = max(a)
    mini = min(a)

    print(maxi, mini)

    value1 = 2 * mini
    value2 = maxi // 2

    print(value1, value2)

    for i in a:
    if i > value1:
    count1 += 1
    if i < value2:
    count2 += 1
    print(‘Remove {} Largest integers’.format(count1))
    print(‘OR’)
    print(‘Remove {} Smallest integers’.format(count2))

  6. Rutger said

    @Daniel: O(n log n) for qsort. However, I think your for + while loop has iterations: 1+2+3+…+n = 1/2n * (n+1) = O(n^2).

  7. Daniel said

    “@Daniel: O(n log n) for qsort. However, I think your for + while loop has iterations: 1+2+3+…+n = 1/2n * (n+1) = O(n^2).”

    @Rutger, I thought the for + while loop is O(n) since both indices i and j are making a single pass across the list in total (unlike a conventional nested for loop, the inner index j is strictly increasing).

    Is your analysis considering this? The 1+2+…+n that you wrote seems like it would arise from an ordinary nested for loop over i from 0 to n and j from 0 to i.

    If possible, can you please provide more details? Thanks.

  8. Klong version 3 — @Daniel – Good call. Thanks. It did not perform as it should have. Made appropriate changes.

    e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]} 
    e1::{:[x>y%2; y-x; x]}
    e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<len%2; :[n2<len%2; :[n1<n2; n1; n2]; n1]; e3(e1(n1; len); e1(n2; len); l2)]}
    e3::{[z1]; z1::z; e2((-x)_y_z)+x+y}
    

    Examples::monad

                {.w(x); .p(" --> ",,/:~e(x))}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [4 5 3 8 3 7] [1 2 20 21 22 200]];"done"
    

    [] –> No solution
    [4][ –> 0]
    [2 2][ –> 0]
    [1 3 5][ –> 1]
    [1 5 5 20][ –> 2]
    [4 5 3 8 3 7][ –> 2]
    [1 2 20 21 22 200][ –> 3]
    “done”

  9. Steve said

    @ProgrammingPraxis: Ran your program on Gambit Scheme with the following tests and it didn’t seem to work for:

    (display (f ‘(1 5 5 20))) (newline)
    1
    >
    (display (f ‘(1 2 20 21 22 200))) (newline)
    1
    >

  10. Globules said

    Here’s an O(n) Haskell version. It makes two passes over the array: first to find the minimum and maximum values, then to count the number of values that are greater than twice the minimum and those that are less than half the maximum. It returns the minimum of these two counts.

    {-# LANGUAGE OverloadedLists #-}
    {-# OPTIONS_GHC -fno-warn-type-defaults #-}
    
    import qualified Control.Foldl as F
    import qualified Data.Vector   as V
    
    -- The minimum number of numbers to remove from an array so that the smallest
    -- remaining value is less than or equal to twice the largest remaining value.
    rem2x :: (Ord a, Num a) => V.Vector a -> Int
    rem2x xs
      | V.length xs == 0 = 0
      | otherwise =
          let (Just min', Just max') = foldp F.minimum F.maximum xs
              (highs, lows) = foldp (count (`gt2` min')) (count (max' `gt2`)) xs
          in min highs lows
      where foldp f g = F.fold ((,) <$> f <*> g)
            count f = F.handles (F.filtered f) F.length    
            x `gt2` y = x > 2 * y
    
    main :: IO ()
    main = do
      print $ rem2x [4, 5, 3, 8, 3, 7]
      print $ rem2x [1, 5, 5, 20]
      print $ rem2x [1, 2, 20, 21, 22, 200]
      print $ rem2x [1, 2]
      print $ rem2x [4]
      print $ rem2x []
    
    $ ./rem2x
    2
    3
    4
    0
    0
    0
    
  11. Daniel said

    @Globules, for [1,5,5,20], it’s possible to remove two elements (1 and 20), but your solution seemingly removes three. While removing three is still valid based on a strict reading of the question, the goal is presumably be to remove as few elements as possible (otherwise, the solution could always be to remove all but one element). For [1, 2, 20, 21, 22, 200], your solution seemingly removes 4 elements, but it’s possible to remove three (1, 2, and 200).

  12. Daniel said

    “@Daniel: O(n log n) for qsort. However, I think your for + while loop has iterations: 1+2+3+…+n = 1/2n * (n+1) = O(n^2).”

    @Rutger, I’ve given more thought to your earlier comment.

    Using the same approach that you used, I think the number of iterations is (1+x1) + (1+x2) + (1+x3) + … + (1+xN), where the 1s are from the outer loop and x’s are from the inner loop. The inner loop executes N times in total, so the sum across x’s is N and the preceding sum would be 2N, making the loop part of the code O(n), and the entire algorithm O(n log n).

    An alternative way to think of the approach I used is that the array is first sorted, and then a sliding window slides over the array by incrementally moving the front and end of the window. Each incremental movement of the front or end of the window is one unit toward the end of the array, resulting in 2N movements (N movements of the front and N movements of the back).

    Additionally, the for + while loop can be seen as O(n) by considering how many times the body of the for loop and the while loop each execute. The body of the for loop executes N times, and the body of the while loop also executes N times. Both of these execute N times in total (as opposed to being executed N times on each iteration).

  13. Zack said

    Interesting drill. Here is my take on it using Julia v. 1.0:

    Code:
    function aoi_engine(x_::Array{<:Integer, 1}, go_with_small_values::Bool = true)
    n_ = length(x_)
    x = copy(x_)
    m, M = extrema(x)
    n = length(x)

    while M > 2*m
        if go_with_small_values
            ind = (1:n)[x .== m]
            deleteat!(x, ind)
            m = minimum(x)
        else
            ind = (1:n)[x .== M]
            deleteat!(x, ind)
            M = maximum(x)
        end
    
        n = length(x)
    end
    
    return n_ - n
    

    end

    function aoi(z::Array{<:Integer, 1})
    c1 = aoi_engine(z)
    c2 = aoi_engine(z, false)

    if c1 < c2
        return c1, "small"
    else
        return c2, "large"
    end
    

    end

    Note: as a bonus, this code yields not only the number of elements that need to be removed, but also the strategy used for keeping that to a minimum

    Example:
    julia> x = [9, 10, 2, 5, 1, 7, 6, 2, 10, 2];
    julia> aoi(x)
    (4, “small”) # output

    So, we need to remove the 4 smallest elements in order to get an array that satisfies the given condition.

    Should we want to explore the other strategy, we can do so as follows:
    julia> aoi_engine(x, false)
    6 # output

    As expected, this yields a larger number. In other words, should we wish to start from the higher values of the array, we’d need to remove 6 elements before the given condition is satisfied.

    I imagine that this drill aims to create a heuristic for removing outliers or elements that could potentially act as outliers. Is that the case?

  14. Globules said

    @Daniel You’re right, I didn’t pay close enough attention to the wording of the problem. So much for working at Amazon…

  15. Klong version 4 – Found a list — [2 3 4 9 19] — which my earlier program did not process correctly

    e::{:[0=#x; "No solution" :|1=#x; 0; e2(x)]}
    e1::{:[x>y%2; y-x; x]}
    e2::{[hi l2 len lo n1 n2]; lo::(l2::x@<x)@0; hi::l2@((len::#l2)-1); n1::(+/{x<hi%2}'l2); n2::(+/{x>(lo*2)}'l2); :[n1<len%2; :[n2<len%2; n1&n2; n1]; :[n2<len%2; n2; e3(e1(n1; len); e1(n2; len); l2)]]}
    e3::{[z1]; z1::z; e2((-x)_y_z)+x+y}
    
    {.w(x," --> ",e(x)); .p("")}'[[] [4] [2 2] [1 3 5] [1 5 5 20] [2 3 4 9 19] [4 5 3 8 3 7] [1 2 20 21 22 200]];"done"
    

    steve@steve-VirtualBox:~/klong$ rlwrap ./kg
    Klong 20180213
    ]l lib/arrayofintegers
    loading “./lib/arrayofintegers.kg”
    [” –> No solution”]
    [4 ” –> ” 0]
    [2 2 ” –> ” 0]
    [1 3 5 ” –> ” 1]
    [1 5 5 20 ” –> ” 2]
    [2 3 4 9 19 ” –> ” 2]
    [4 5 3 8 3 7 ” –> ” 2]
    [1 2 20 21 22 200 ” –> ” 3]

  16. Heres a C++ solutionm runs in O(n log n), returns the minimum number of elements to remove.

    #define bsearch(a,n) (upper_bound(begin(a),end(a),n)-begin(a))

    int minRemove(vector<int> arr) {
    sort(begin(arr), end(arr));
    int i=0, s=(int)arr.size(), m=s+1, bi;
    while (i < s){
    if (i >= m) break;
    bi = bsearch(arr, 2*arr[i]);
    m = min(m, i+s-bi);
    i+=1;
    }
    return m;
    }

    int main() {
    vector<int> a = {3,4,4,5,5,6};
    vector<int> b = {3,4,4,5,7,8,9};

    cout << minRemove(a) << endl;
    cout << minRemove(b) << endl;
    }

    /*
    0
    2
    */

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: