ArrayIndexOutOfBounds exception in hackerrank Cut the sticks

Question

I am trying to implement a problem in Hackerrank Cut the sticks. Problem can be found here my code is this

static int[] cutTheSticks(int[] arr) 
{
    int n = arr.Length, k = 0;
    int[] result = new int[n];
    Array.Sort(arr);
    Array.Reverse(arr);

    while(arr.Length != 0)
    {
        result[k] = arr.Length;
        k++;

        for(int i = 0; i < n; ++i)
        {
            arr[i] -= arr[arr.Length - 1];
        } 
    }

    return result;
}

it shows error as-

System.IndexOutOfRangeException: Index was outside the bounds of the array.
at Solution.cutTheSticks (System.Int32[] arr) [0x00020] in solution.cs:24

line 24 is:

result[k] = arr.Length;

How to remove this?

Possible duplicate of [What is an IndexOutOfRangeException / ArgumentOutOfRangeException and how do I fix it?](https://stackoverflow.com/questions/20940979/what-is-an-indexoutofrangeexception-argumentoutofrangeexception-and-how-do-i-f) — SᴇM, Nov 18 '19 at 08:40
Considering that you don't remove any elements from `arr`, when will `arr.Length!=0` ever become false? Think about what happens inside your infinite loop, for example with `k` and `result[k]`... — Some programmer dude, Nov 18 '19 at 08:40
@Someprogrammerdude yeah I understand that loop is running for infinite times. How to remove the element ? — Mr. A, Nov 18 '19 at 08:43

score 1 · Answer 1 · answered Nov 18 '19 at 09:04

There are several problems with your code. To name a few:

You are giving the result array a fixed size (int[] result=new int[n];), but it's size depends entirely on how many duplicate values are contained in the list.

You are supposed to remove from the array the smallest value(s) in each iteration. However you are just modifying the values (arr[i] -= arr[arr.Length - 1];), not removing them, so the array length will remain the same, and thus while (arr.Length != 0) will always be true, creating an endless loop. This causes k++ to keep incrementing until it reaches a value greater than the array length, which then results in the exception you are getting.

Since you are supposed to change the size of the input array, I suggest using List<int> instead, here's an example:

List<int> output = new List<int>();
List<int> input = new List<int>(arr);

while (input.Count > 0)
{
    output.Add(input.Count);
    int min = input.Min();
    input.RemoveAll(x => x == min);
    input.ForEach(x => x -= min);
}

return output.ToArray();

StepUp · Answer 2 · 2019-11-18T09:25:16.560

It is necessary to add condition k < n before assigning value to avoid IndexOutOfRangeException exception. In addition, there is a strong need a condition to avoid infinite while loop :

static int[] cutTheSticks(int[] arr) {
    int n = arr.Length,
            k = 0;
    int[] result = new int[n];
    Array.Sort(arr);
    Array.Reverse(arr);
    while (arr.Length != 0)
    {
            if (k < n)
                result[k] = arr.Length;
            else
                break;
            k++;
            for (int i = 0; i < n; ++i)
            {
                arr[i] -= arr[arr.Length - 1];
            }
    }
    return result;
}

UPDATE:

It is possible to pop out one element after every iteration like this:

static int[] cutTheSticks(int[] arr)
{
    int n = arr.Length,
            k = 0;
    int[] result = new int[n];
    var arrToBeRemoved = arr.ToList();
    Array.Sort(arr);
    Array.Reverse(arr);
    while (arr.Length != 0)
    {
        if (k < n)
            result[k] = arr.Length;
        else
            break;

        if (k < arrToBeRemoved.Count)
            arrToBeRemoved.RemoveAt(k);

        arr = arrToBeRemoved.ToArray();
        k++;
        for (int i = 0; i < arr.Length; ++i)
        {
            arr[i] -= arr[arr.Length - 1];
        }
     }
     return result;
}

that worked but in the last i want to pop out one element after every iteration, Can u suggest a solution for the same? — Mr. A, Nov 18 '19 at 09:08

score 0 · Answer 3 · answered Nov 18 '19 at 10:35

I would do it that way:

static int[] cutTheSticks(int[] arr)
{
    List<int> results = new List<int>();
    int cutted = 0;
    while (cutted != 1)
    {
        cutted = 0;
        int min = GetMin(arr);
        if (min == 0)
        {
            break;
        }
        for (int i = 0; i < arr.Length; i++)
        {
            if (arr[i] >= min)
            {
                arr[i] -= min;
                cutted++;
            }
        }
        results.Add(cutted);
    }
    return results.ToArray();
}

static int GetMin(int[] arr)
{
    int min = int.MaxValue;
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] != 0 && arr[i] < min)
        {
            min = arr[i];
        }
    }
    return min;
}

ArrayIndexOutOfBounds exception in hackerrank Cut the sticks

3 Answers3