How to dynamically add indexes values of an array in C#?

Question

I have an array where the first two smallest values have to be added, and consequently the result has to be added to next smallest and so on until it reaches the end of the array to give a final total.

However, how can I dynamically modify the method/function so if the values changes and I have 6 vehicles and 6 specs values in the array, the return of the method/function total is not restricted to just 4 indexes.

The array values are unsorted, so in order to add the first smallest, it has to be sorted. Once that's done it adds the values of the new array.

Here's what I've tried:

public static int vehicles = 4;
public static int[] specs = new int[] { 40, 8, 16, 6 };

public static int time(int vehicles, int[] specs)
{
    int newValue = 0;

    for (int i = 1; i < vehicles; i++)
    {
        newValue = specs[i];
        int j = i;

        while (j > 0 && specs[j - 1] > newValue)
        {
            specs[j] = specs[j - 1];
            j--;
        }
        specs[j] = newValue;
    }

    // How can I dynamically change this below:
    int result1 = specs[0] + specs[1];
    int result2 = result1 + specs[2];
    int result3 = result2 + specs[3];
    int total = result1 + result2 + result3;

    return total; // Returns 114
}

Here's the idea of how it works:

4, [40, 8, 16, 6] = 14 --> [40, 14, 16] = 30 --> [40, 30] = 70 ==>> 14 + 30 + 70 = 114
6, [62, 14, 2, 6, 28, 41 ] = 8 --> [62, 14, 8, 28, 41 ] --> 22 [62, 22, 28, 41 ] --> 50 
   [62, 50, 41 ] --> 91 [62, 91 ] --> 153 ==> 8 + 22 + 50 + 91 + 153 = 324

Answer 1

First off, if you are not restricted to arrays for some weird reason use List<int> and your life will be easier.

List<int> integers = { 14, 6, 12, 8 };

integers.Sort();

integers.Reverse();

while( integers.Count > 1 )
{
    int i = integers[integers.Count - 1];
    int j = integers[integers.Count - 2];
    integers[integers.Count - 2] = i + j;
    integers.RemoveAt(integers.Count - 1);
}

var result = integers[0];

P.S.: This can be easily modified to operate on the array version, you can't RemoveAt() from an array but can separately maintain a lastValidIndex.

Answer 2

See comments in code for explanation.

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        //var inputs = new [] { 40, 8, 16, 6 }; // total = 114
        var inputs = new[] { 62, 14, 2, 6, 28, 41 }; // total = 324

        var total = 0;
        var query = inputs.AsEnumerable();
        while (query.Count() > 1)
        {
            // sort the numbers
            var sorted = query.OrderBy(x => x).ToList();
            // get sum of the first two smallest numbers
            var sumTwoSmallest = sorted.Take(2).Sum();
            // count total
            total += sumTwoSmallest;
            // remove the first two smallest numbers
            query = sorted.Skip(2);
            // add the sum of the two smallest numbers into the numbers
            query = query.Append(sumTwoSmallest);
        }
        Console.WriteLine($"Total = {total}");

        Console.WriteLine("Press any key...");
        Console.ReadKey(true);
    }
}

I benchmark my code and the result was bad when dealing with large dataset. I suspect it was because of the sorting in the loop. The sorting is needed because I need to find the 2 smallest numbers in each iteration. So I think I need a better way to solve this. I use a PriorityQueue (from visualstudiomagazine.com) because the elements are dequeued based on priority, smaller numbers have higher priority in this case.

long total = 0;
while (pq.Count() > 0)
{
    // get two smallest numbers when the priority queue is not empty
    int sum = (pq.Count() > 0 ? pq.Dequeue() : 0) + (pq.Count() > 0 ? pq.Dequeue() : 0);
    total += sum;
    // put the sum of two smallest numbers in the priority queue if the queue is not empty
    if (pq.Count() > 0) pq.Enqueue(sum);
}

Here's some benchmark results of the new (priority queue) code and the old code in release build. Results are in milliseconds. I didn't test the 1 million data with the old code because it's too slow.

+---------+----------+-------------+
|  Data   |   New    |     Old     |
+---------+----------+-------------+
|   10000 |   3.9158 |   5125.9231 |
|   50000 |  16.8375 | 147219.4267 |
| 1000000 | 406.8693 |             |
+---------+----------+-------------+

Full code:

using System;
using System.Diagnostics;
using System.IO;
using System.Linq;

class Program
{
    static void Main()
    {
        const string fileName = @"numbers.txt";
        using (var writer = new StreamWriter(fileName))
        {
            var random = new Random();
            for (var i = 0; i < 10000; i++)
                writer.WriteLine(random.Next(100));
            writer.Close();
        }

        var sw = new Stopwatch();

        var pq = new PriorityQueue<int>();
        var numbers = File.ReadAllLines(fileName);
        foreach (var number in numbers)
            pq.Enqueue(Convert.ToInt32(number));

        long total = 0;
        sw.Start();
        while (pq.Count() > 0)
        {
            // get two smallest numbers when the priority queue is not empty
            int sum = (pq.Count() > 0 ? pq.Dequeue() : 0) + (pq.Count() > 0 ? pq.Dequeue() : 0);
            total += sum;
            // put the sum of two smallest numbers in the priority queue if the queue is not empty
            if (pq.Count() > 0) pq.Enqueue(sum);
        }
        sw.Stop();
        Console.WriteLine($"Total = {total}");
        Console.WriteLine($"Time = {sw.Elapsed.TotalMilliseconds}");

        total = 0;
        var query = File.ReadAllLines(fileName).Select(x => Convert.ToInt32(x));
        sw.Restart();
        while (query.Count() > 0)
        {
            // sort the numbers
            var sorted = query.OrderBy(x => x).ToList();
            // get sum of the first two smallest numbers
            var sumTwoSmallest = sorted.Take(2).Sum();
            // count total
            total += sumTwoSmallest;
            // remove the first two smallest numbers
            query = sorted.Skip(2);
            // add the sum of the two smallest numbers into the numbers
            if (query.Count() > 0)
                query = query.Append(sumTwoSmallest);
        }
        sw.Stop();
        Console.WriteLine($"Total = {total}");
        Console.WriteLine($"Time = {sw.Elapsed.TotalMilliseconds}");

        Console.WriteLine("Press any key...");
        Console.ReadKey(true);
    }
}

PriorityQueue code:

using System;
using System.Collections.Generic;

// From http://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data;

    public PriorityQueue()
    {
        this.data = new List<T>();
    }

    public void Enqueue(T item)
    {
        data.Add(item);
        int ci = data.Count - 1; // child index; start at end
        while (ci > 0)
        {
            int pi = (ci - 1) / 2; // parent index
            if (data[ci].CompareTo(data[pi]) >= 0)
                break; // child item is larger than (or equal) parent so we're done
            T tmp = data[ci];
            data[ci] = data[pi];
            data[pi] = tmp;
            ci = pi;
        }
    }

    public T Dequeue()
    {
        // assumes pq is not empty; up to calling code
        int li = data.Count - 1; // last index (before removal)
        T frontItem = data[0];   // fetch the front
        data[0] = data[li];
        data.RemoveAt(li);

        --li; // last index (after removal)
        int pi = 0; // parent index. start at front of pq
        while (true)
        {
            int ci = pi * 2 + 1; // left child index of parent
            if (ci > li)
                break;  // no children so done
            int rc = ci + 1;     // right child
            if (rc <= li && data[rc].CompareTo(data[ci]) < 0) // if there is a rc (ci + 1), and it is smaller than left child, use the rc instead
                ci = rc;
            if (data[pi].CompareTo(data[ci]) <= 0)
                break; // parent is smaller than (or equal to) smallest child so done
            T tmp = data[pi];
            data[pi] = data[ci];
            data[ci] = tmp; // swap parent and child
            pi = ci;
        }
        return frontItem;
    }

    public T Peek()
    {
        T frontItem = data[0];
        return frontItem;
    }

    public int Count()
    {
        return data.Count;
    }

    public override string ToString()
    {
        string s = "";
        for (int i = 0; i < data.Count; ++i)
            s += data[i].ToString() + " ";
        s += "count = " + data.Count;
        return s;
    }

    public bool IsConsistent()
    {
        // is the heap property true for all data?
        if (data.Count == 0)
            return true;
        int li = data.Count - 1; // last index
        for (int pi = 0; pi < data.Count; ++pi)
        { // each parent index
            int lci = 2 * pi + 1; // left child index
            int rci = 2 * pi + 2; // right child index

            if (lci <= li && data[pi].CompareTo(data[lci]) > 0)
                return false; // if lc exists and it's greater than parent then bad.
            if (rci <= li && data[pi].CompareTo(data[rci]) > 0)
                return false; // check the right child too.
        }
        return true; // passed all checks
    }
    // IsConsistent
}
// PriorityQueue

Reference:

• https://visualstudiomagazine.com/articles/2012/11/01/priority-queues-with-c.aspx
• https://en.wikipedia.org/wiki/Priority_queue

Answer 3

I would go with the simplest version of a one line solution using LINQ:

Array.Sort(specs);
int total = specs.Select((n, i) => specs.Take(i + 1).Sum()).Sum() - (specs.Length > 1 ? specs[0] : 0);

Answer 4

I would use Linq.

Enumerable.Range(2, specs.Length - 1)
    .Select(i => specs
        .Take(i)
        .Sum())
    .Sum();

Explanation:

1. We take a range starting from 2 ending with specs.Length.
2. We sum the first i values of specs where i is the current value in the range.
3. After we have all those sums, we sum them up as well.

To learn more about linq, start here.

This code only works if the values have been sorted already.
If you want to sort the values using linq, you should use this:

IEnumerable<int> sorted = specs.OrderBy(x => x);

Enumerable.Range(2, sorted.Count() - 1)
    .Select(i => sorted
        .Take(i)
        .Sum())
    .Sum();

The OrderBy function needs to know how to get the value it should use to compare the array values. Because the array values are the values we want to compare we can just select them using x => x. This lamba takes the value and returns it again.

Answer 5

You can simply sort it using Array.Sort(), then get the sums in a new array which starts with the smallest value and add each next value to the most recent sum, the total will be the value of the last sum.

public static int time(int vehicles, int[] specs)
{
    int i, total;
    int[] sums = new int[vehicles];
    Array.Sort(spec);
    sums[0] = specs[0];
    for (i = 1; i < vehicles; i++)
        sums[i] = sums[i - 1] + spec[i];
    total = sums[spec - 1];
}