CODEWITHSUNDEEP
arraysalgorithm
lebesgue
lebesgue

Reputation: 1113

Modify the array to minimize the difference

You are given an array A of n values and a value k. You have to either increase or decrease every element in A by k and must do it only once for every element. The goal is to minimize the difference between the largest and the smallest elements in the resulting array A (after modification) and output this difference.

For example, A=[1,7], k=4, we need to modify A as [5,3], then the difference is 2, which is the minimum difference we can achieve.

Can anyone help me on how to solve this question?

Upvotes: 4

Views: 1029

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Here's one way to think about it (imagine a sorted array, x's are a[i] + k and y's are a[i] - k)

x
  x
      x
           x
y              
  y             x[i](min?)
      y                   x
           y                  x[n-1]
                y[i](min?)     
                          y   
                              y

If you choose y[i] as the minimum, your choice for maximum would be:

max( y[0], x[i + 1] )

And if you choose x[i] as the minimum...oh you can't since any a[j] ± k, j > i must be smaller in this sorted arrangement.

If you choose x[n-1] as the minimum, your choice for maximum would be the largest of all min(x[j],y[j]) where both x[j] and y[j] are greater than or equal to x[n-1] (or just x[j] if y[j] < x[n-1]).

If you choose y[0] as the minimum, your choice for maximum would be max(x[j]), provided that all x[j] are greater than or equal to y[0].

Upvotes: 1

Ayoub Falah
Ayoub Falah

Reputation: 484

Here is an algorithm with an order of O(n*log(n)):

public class MinDiff 
{
    public static void main(String[] args) 
    {
        int A[] = {1,7};
        int k = 4;
        System.out.println("Input a:=" + Arrays.toString(A) + ", k:=" + k);
        find(A, k);
        System.out.println("Output a´:=" + Arrays.toString(A));
    }

    private static void find(int a[], int k) 
    {       
        Arrays.sort(a);

        int n = a.length;
        if (k > a[n - 1] - a[0])
        {
            for (int i = 0; i < n; i++)
                a[i] += k;
            return;
        }

        a[0] = a[0] + k;
        a[n - 1] = a[n - 1] - k;

        int max = Math.max(a[0], a[n - 1]);
        int min = Math.min(a[0], a[n - 1]);

        for (int index = 1; index < n - 1; index++) 
        {
            if (a[index] < min)
                a[index] += k;
            else if (a[index] > max)
                a[index] -= k;
            else if ((a[index] - min) > (max - a[index]))
                a[index] -= k;
            else
                a[index] += k;

            max = Math.max(a[index], max);
            min = Math.min(a[index], min);
        }
    }
}

Input: a:=[1, 7], k:=4

Output: a´:=[5, 3]

Upvotes: 0

Vedang Mehta
Vedang Mehta

Reputation: 2254

My recursive dynamic programming solution in C++.The time complexity is O(N3)-

    #include <iostream>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <limits>

    using namespace std;

    vector <int> v;
    map < pair <int, pair <int,int> >, int > mp;

    int k, n;

    int solve(int index, int minimum, int maximum)
    {
            if(index == n)
                    return maximum - minimum;
            pair <int, pair <int,int> > p = pair <int, pair <int,int> > (index, pair <int,int> (minimum, maximum));
            if(mp.find(p) != mp.end())
                    return mp[p];
            int x = v[index] - k, y = v[index] + k;
            return mp[p] = min(solve(index + 1, min(x, minimum), max(x, maximum)), solve(index + 1, min(y, minimum), max(y, maximum)));
    }

    int main()
    {
            int p = std::numeric_limits<int>::max();
            int q = std::numeric_limits<int>::min();
            cin >> k >> n;
            int x;
            for(int i = 0;i < n;i++)
            {
                    cin >> x;
                    v.push_back(x);
            }
            cout << solve(0, p, q) << endl;
            return 0;
    }

Upvotes: 0

Related Questions