3
\$\begingroup\$

The assumption is that k is quite large as compared to no. of elements in the array and division by 2 returns ceiling of the result.

Request for your review and suggestions for further improvements or simplifications.

Example : Array: { 10, 15, 7, 23, 5}

k = 6

Solution: {5, 4, 4, 6, 5} = 24

How Code Works?

Basically we are taking the maximum element and diving it by 2 for example in the first step we take 23 and return 12, as the ceiling of 23/2.

We need to repeat the above steps for k times to get the minimized sum of 24.

As the above algorithm is of the complexity O(kn) so to reduce the complexity I am dividing the array to sub arrays based upon their log2 values, so the no. of k and n gets reduced to very small numbers.

Code:

    private static int GetMinSum(int[] array, int k)
    {
        int n = array.Length;
        var sum = 0;
        k = GetOptimizedListAndK(array, n, k, out var lists);

        //If more sublists are needed  
        if (k > 0)
        {
            var count = lists.CountSum;
            var key = lists.Key;
            if (key > 0)
            {
                var poweroftwo = 1 << key;
                sum += count * poweroftwo - k * poweroftwo / 2;
                var dictionary2 = GetDictionary(array, lists, poweroftwo);
                key = dictionary2.Keys.Last();

                while (k > 0 && key > 0)
                {

                    var list2 = dictionary2[key];
                    count = list2.Count;
                    if (k >= count)
                    {
                        list2.ForEach(
                             index => array[index] = array[index] / 2 + array[index] % 2);


                        dictionary2.Remove(key);

                        key = dictionary2.Keys.LastOrDefault();

                        k -= count;
                    }
                    else
                    {
                        if (k <= Log2(count))
                        {

                            for (int i = 0; i < k; i++)
                            {

                                var indexAtMax = GetMaxIndex(list2, array);
                                array[indexAtMax] = array[indexAtMax] / 2 + array[indexAtMax] % 2;
                            }
                            k = 0;
                        }
                        if (count - k <= Log2(count))
                        {
                            var minIndexes = GetMinIndexes(list2, array, count - k);

                            foreach (var i in list2)
                            {
                                if (!minIndexes.Contains(i))
                                {
                                    array[i] = array[i] / 2 + array[i] % 2;
                                }
                            }

                            k = 0;
                        }
                        if (k > 0)
                        {
                            poweroftwo = 1 << key;
                            sum += list2.Count * poweroftwo - k * poweroftwo / 2;
                            dictionary2 = GetDictionary(array, list2, poweroftwo);
                            key = dictionary2.Keys.Last();
                        }
                    }
                }
            }
        }
        return array.Sum() + sum;
    }
    private static int GetOptimizedListAndK(int[] array, int n, int k, out Lists lists)
    {
        lists = null;
        Dictionary<int, Lists> dictionary = new Dictionary<int, Lists>();
        PopulatePowerBasedDictionary(array, n, dictionary);
        var key = dictionary.Keys.Max();
        while (key > 0 && k > 0)
        {
           lists = dictionary[key];
           var count = lists.CountSum;

            if (k >= count)
            {
                lists.ForEach(list => list.ForEach(index => array[index] = array[index] / 2 + array[index] % 2));
                if (key > 1)
                {
                    if (dictionary.TryGetValue(key - 1, out var lowerlists))
                    {
                        lowerlists.AddRange(lists);
                        lowerlists.CountSum += count;
                    }
                    else dictionary.Add((key - 1), lists);
                }

                dictionary.Remove(key);

                key--;

                k -= count;
            }
            else
            {
                if (k < Log2(count))
                {
                    for (int i = 0; i < k; i++)
                    {
                        var indexAtMax = GetMaxIndex(lists, array);
                        array[indexAtMax] = array[indexAtMax] / 2 + array[indexAtMax] % 2;
                    }
                    k = 0;
                }
                if (count - k < Log2(count))
                {
                    var minIndexes = GetMinIndexes(lists, array, count - k);
                    foreach (var list in lists)
                    {
                        foreach (var i in list)
                        {
                            if (!minIndexes.Contains(i))
                            {
                                array[i] = array[i] / 2 + array[i] % 2;
                            }
                        }
                    }
                    k = 0;
                }
                break;
            }
        }
        return k;
    }

    private static void PopulatePowerBasedDictionary(int[] array, int n, Dictionary<int, Lists> dictionary)
    {
        for (int i = 0; i < n; i++)
        {
            if (array[i] < 2) continue;
            var log2 = Log2(array[i]);
            if (dictionary.TryGetValue(log2, out var lists))
            {
                lists[0].Add(i);
                lists.CountSum++;
            }
            else
            {
                lists = new Lists(1,log2) { new List<int> { i } };
                dictionary.Add(log2, lists);
            }
        }
    }

    private static int GetMaxIndex(List<int> list, int[] array)
    {
        var maxIndex = 0;
        var max = 0;

        foreach (var i in list)
        {
            if (array[i] > max)
            {
                maxIndex = i;
                max = array[i];
            }
        }

        return maxIndex;
    }

    private static SortedDictionary<int, List<int>> GetDictionary(int[] array, Lists lists, int poweroftwo)
    {
        SortedDictionary<int, List<int>> dictionary = new SortedDictionary<int, List<int>>();


        foreach (var list in lists)
        {
            foreach (var i in list)
            {
                array[i] = array[i] - poweroftwo;
                if (array[i] < 2)
                {
                    continue;
                }
                var log2 = Log2(array[i]);
                if (dictionary.TryGetValue(log2, out var list2))
                {
                    list2.Add(i);
                }
                else
                {
                    list2 = new List<int> { i };
                    dictionary.Add(log2, list2);
                }

            }
        }

        return dictionary;
    }
    private static SortedDictionary<int, List<int>> GetDictionary(int[] array, List<int> list, int poweroftwo)
    {
        SortedDictionary<int, List<int>> dictionary = new SortedDictionary<int, List<int>>();

        foreach (var i in list)
        {
            array[i] = array[i] - poweroftwo;
            if (array[i] < 2)
            {
                continue;
            }
            var log2 = Log2(array[i]);
            if (dictionary.TryGetValue(log2, out var list2))
            {
                list2.Add(i);
            }
            else
            {
                list2 = new List<int> { i };
                dictionary.Add(log2, list2);
            }


        }

        return dictionary;
    }
    private static int GetMaxIndex(Lists lists, int[] array)
    {
        var maxIndex = 0;
        var max = 0;
        foreach (var list in lists)
        {
            foreach (var i in list)
            {
                if (array[i]>max)
                {
                    maxIndex = i;
                    max = array[i];
                }
            }
        }
        return maxIndex;
    }
    private static HashSet<int> GetMinIndexes(Lists lists, int[] array, int k)
    {
        var mins = new HashSet<int>();
        var minIndex = 0;
        var min = int.MaxValue;
        for (int j = 0; j < k; j++)
        {
            foreach (var list in lists)
            {
                foreach (var i in list)
                {
                    if (array[i] < min && !mins.Contains(i))
                    {
                        minIndex = i;
                        min = array[i];
                    }
                }
            }
            mins.Add(minIndex);
            min = int.MaxValue;
        }

        return mins;
    }
    private static HashSet<int> GetMinIndexes(List<int> list, int[] array, int k)
    {
        var mins = new HashSet<int>();
        var minIndex = 0;
        var min = int.MaxValue;
        for (int j = 0; j < k; j++)
        {

                foreach (var i in list)
                {
                    if (array[i] < min && !mins.Contains(i))
                    {
                        minIndex = i;
                        min = array[i];
                    }
                }
            mins.Add(minIndex);
            min = int.MaxValue;
        }

        return mins;
    }
    private static int Log2(int n)
    {
        return BitOperations.Log2((uint)n);
    }

Lists Class:

public class Lists:List<List<int>>
{
    public int Key { get; set; }
    public int CountSum { get; set; }

    public Lists(int countSum, int key):base()
    {
        CountSum = countSum;
        Key = key;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Any reason why your algorithm is so complex? I would say this is a few lines solution: sort array, remove last element from list (max element), divide by 2, insert element into proper place to keep array sorted. Repeat k times. \$\endgroup\$ – Peska May 17 '20 at 13:09
  • \$\begingroup\$ @Peska insert into proper place, to get that only I have divided into sub lists, and sorting is not needed if k>length of a sublist. The logic is that if you group based upon log2 of the value, you can always move to adjacent lower sublist when divoided by 2. \$\endgroup\$ – Deepak Mishra May 17 '20 at 13:22
  • \$\begingroup\$ If the maximum element is duplicated, is only one of them divided by two? \$\endgroup\$ – NetMage Oct 7 '20 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.