Umbrella Challenge

A-umbrella.md

Umbrella Challenge

Given a number of people N and an array of integers, each one representing the amount of people a type of umbrella can handle, output the minimum number of umbrellas needed to handle N people.

No umbrella could have left spaces. Which means if a umbrella can handle 2 people, there should be 2 people under it.

If there's no solution, return -1.

Examples

solve(3, [1, 2]) means that we have 3 people and two kinds of umbrellas, one that hanled one person and one that handles 2. We can give one two-sized umbrella to 2 of them and the other to the last person. Therefore the solution is 2 (umbrellas). You could give 3 one-sized umbrellas, but we want the minimum number.

solve(10, [3, 1]). You can give 3 three-sized umbrellas and 1 one-sized. This means the solution is 4.

solve(3, [2]). There's no solution since one umbrella would have empty space. Return -1.

B-umbrella.js

function solve(n, umbrellas) {
  return -1
}

const tests =
[ { n: 3
  , umbrellas: [1, 2]
  , expect: 2
  }
  
, { n: 10
  , umbrellas: [3, 1]
  , expect: 4
  }

, { n: 3
  , umbrellas: [2]
  , expect: -1
  }
]

tests.forEach(({n, umbrellas, expect}) =>
  console.log(`solve(${n}, [${umbrellas}])`)        ||
  console.log(`   Expects: ${expect}`)              ||
  console.log(`   Output:  ${solve(n, umbrellas)}`) ||
  console.log()
)

Here's My attempt(not the best possible way)

https://github.com/onkar2405/New1/edit/master/Untitled-1.cpp

It can be done by DP not greedy solution
for example array = {1,5,6,9}, n=11 ;
Ans = 3 (9,1,1) Correct Ans 2 (5,6)

Java solution
private static int getMinCount(int[] arr, int n) {
if (arr == null || arr.length == 0 || n < 1)
return -1;
int i = arr.length - 1;
Arrays.sort(arr);
int count = 0;
while (n >= 0 && i >= 0) {
count += n / arr[i];
n = n % arr[i];
i--;
}
return n != 0 ? -1 : count;
}

Can you share the DP approach solution?

Here is my DP solution in Python.
https://gist.github.com/chrysmur/03681d97a414af6d587e1f83820ccaed

C# Solution

1st Solution but did not solve all test cases 
for example array = {1,5,6,9}, n=11 ;
Ans = 3 (9,1,1) Correct Ans 2 (5,6)
 public static int getUmbrellas(int requirement, List<int> sizes)
    {
        sizes.Sort();
        sizes.Reverse();
        int rem = int.MaxValue, result = 0, divisor = 0;
        foreach (var size in sizes)
            if (requirement != 0 && rem != 0 && rem >= size)
            {
                divisor = requirement / size;
                rem = requirement % size;
                requirement = rem;
                result += divisor;
            }
        return rem == 0 ? result : -1;
    }

2nd Solution solved all cases
 public static int getUmbrellas(int r, List<int> sizes)
    {
        //int count = umbrella_count(requirement, sizes);
        //return count != 0 ? -1 : count;
        int n = sizes.Count;
        int[,] graph = new int[n + 1, r + 1];

        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= r; j++)
            {
                if (j == 0)
                    graph[i, j] = 0;
                else if (i == 0)
                    graph[i, j] = (int)Math.Pow(10, 4);
                else if (sizes[i - 1] > j)
                    graph[i, j] = graph[i - 1, j];
                else
                    graph[i, j] = Math.Min(1 + graph[i, j - sizes[i - 1]], graph[i - 1, j]);
            }
        }


        return graph[n, r] >= Math.Pow(10, 4) ? -1 : graph[n, r];
    }

Test Cases

    Console.WriteLine(getUmbrellas(8, new List<int>() { 3, 5 }));
        Console.WriteLine(getUmbrellas(11, new List<int>() { 1, 5, 6, 9 }));
        Console.WriteLine(getUmbrellas(8, new List<int>() { 5, 4, 4, 2 }));
        Console.WriteLine(getUmbrellas(7, new List<int>() { 3, 5 }));
        Console.WriteLine(getUmbrellas(5, new List<int>() { 3, 5 }));
        Console.WriteLine(getUmbrellas(755, new List<int>() { 151, 6, 19, 46, 27, 26, 25, 42, 20, 17, 15, 45, 5, 20, 3, 1, 48, 46, 43, 5, 18, 16, 48, 48, 34, 48, 25, 29, 25, 32, 5, 23, 5, 15, 31, 17, 28, 34, 11, 38, 48, 40, 40, 40, 6, 5, 47, 25, 49, 3, 50, 28, 3, 23, 37, 45, 28, 18, 36, 6, 49, 8, 35, 39, 42, 31, 44, 6, 42, 5, 22, 36, 12, 4, 20, 42, 45, 36, 8, 5, 26, 5, 12, 50, 30, 19, 44, 19, 45, 41, 12, 48, 46, 50, 30, 38, 18, 19, 36, 5, 25, 39, 19, 28, 36, 22, 13, 46, 17, 6, 22, 25, 13, 1, 21, 24, 29, 3, 38, 6, 39, 6, 42, 33, 38, 38, 35, 30, 12, 49, 21, 19, 24, 15, 5, 44, 27, 12, 22, 49, 41, 1, 49, 49, 28, 3, 17, 45, 3, 27, 47, 50, 46, 4, 13, 28, 35, 49, 4, 27, 9, 32, 11, 35, 15, 23, 50, 32, 35, 30, 20, 46, 37, 3, 46, 15, 48, 48, 3, 45, 20, 23, 6, 32, 17, 14, 9, 10, 33, 24, 20, 18, 12, 30, 14, 4, 19, 49, 13, 50, 23, 35, 2, 27, 14, 16, 21, 41, 31, 35, 14, 9, 7, 46, 4, 42, 48, 48, 21, 37, 30, 31, 46, 21, 5, 47, 44, 44, 28, 3, 9, 2, 21, 19, 39, 41, 25, 50, 50 }));