# C# code for minimizing the sum of an array by dividing it's elements (repetition allowed) by 2 for k times

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.CountSum += count;
}
}

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.CountSum++;
}
else
{
lists = new Lists(1,log2) { new List<int> { i } };
}
}
}

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))
{
}
else
{
list2 = new List<int> { i };
}

}
}

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))
{
}
else
{
list2 = new List<int> { i };
}

}

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];
}
}
}
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];
}
}
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;
}
}

• 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. Commented May 17, 2020 at 13:09
• @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. Commented May 17, 2020 at 13:22
• If the maximum element is duplicated, is only one of them divided by two? Commented Oct 7, 2020 at 23:07