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()
)

My solution ⭐ 🐱
https://gist.github.com/anabastos/6e142c6b9bf325cabe97fc3d16ef3e14

https://gist.github.com/Woodsphreaker/0caeedc8ba762ab51395e4eefc6fddd2

https://gist.github.com/adrifmonte/ee0b99df1ddb567860c5a6638e2e1a7d

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

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

Javascript Solution -

function solve(n, umbrellas){
    if(umbrellas.length == 1){
        return n % umbrellas[0] == 0 ? parseInt(n / umbrellas[0]) : -1;
    }

    var max = Math.max(...umbrellas);
    var quotient =  parseInt(n / max);
    var remainingPersons =  n % max;
    
    if(remainingPersons == 0){
        return quotient;
    }else{
        var remainingUmbrellas = umbrellas.filter(function(o){return o != max});
        var value = numberOfUmbrellas(remainingPersons, remainingUmbrellas);
        
        return (value != -1) ? quotient + value : value;
    }   
}

This question is exactly same as "coin change problem" where we have infinite number of coins of each type and we have to find minimum number of coins to make change. One can practice here.

This is my solution

def solve(n,sumbrella):
    for i in sumbrella:
        print("\t Try with type",i)
        if i > n:
            print("Is big try with next")
            next
        q = n // i #quotient
        r = n % i  # remainder
        print(n//i)
        print(n%i)
        if r == 0:
            print("The solution is: ",q)
            return True
        if r in sumbrella:
            print("The solution is:", q+1)
            return True
        else:
            print("Fail")
    return -1

import array
people = 11
umbrella = [1,5,6,9] #add more types for more tests
print(umbrella)
sumbrella = sorted(umbrella,reverse=True)
print(sumbrella)
solve(people,sumbrella)

[1, 5, 6, 9, 11]
[11, 9, 6, 5, 1]
	 Try with type 11
1
0
The solution is:  1





True

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