Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.


Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.


Note:


       The number of nodes in the graph will be in the range [2, 15].
       You can print different paths in any order, but you should keep the order of nodes inside one path.

Difficulty: interview

Starter code:

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        

Solutions:
class Solution:
     def numRabbits(self, answers):
         cnts = collections.Counter(answers)
         return sum(-v % (k+1) + v for k, v in cnts.items())

class Solution:
     def numRabbits(self, answers):
         if not answers: return 0
         
         answers.sort()        
         ht = dict( list(zip(list(set(answers)), [0]*len(set(answers)))) )
         for e in answers:
             ht[e] += 1
         
         min_count = 0
         for e in set(answers):
             group, count = e, ht[e]
             
             if count <= group + 1:
                 min_count += group + 1
             else:
                 #apply pigeonhole principle
                 a, b = divmod(count, group + 1)
                 min_count += (a + (b>0)) * (group + 1)
         
         return min_count
             


class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         if not answers:
             return 0
         count = collections.Counter(answers)
         res = 0
         for key, value in count.items():
             if key == 0:
                 res += count[0]
             else:
                 if key+1 > value:
                     res += (key+1)
                 else:
                     if value % (key+1) == 0:
                         res += value
                     else:
                         res += (key+1)*(value//(key+1)+1)
         return res

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         if not answers:
             return 0
 
         rabbits = 0
         answers = sorted(answers)
         n = len(answers)
         not_count = 0
         iteration = 1
         prev_value = 0
 
         for i in range(n):
             if iteration >= not_count \
                     or prev_value != answers[i]:
                 rabbits += answers[i] + 1
                 iteration = 0
                 not_count = answers[i] + 1
                 prev_value = answers[i]
 
             iteration += 1
 
         return rabbits

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         rabbit = {}
         for n in set(answers):
             rabbit[n] = answers.count(n)
         res = 0
         for i in rabbit.keys():
             res += math.ceil(rabbit[i]/(i+1)) * (i+1)
         return res

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         answers.sort()
         answers_len = len(answers)
         result = 0
         index = 0
         while True:
             if index >= answers_len:
                 break
             if answers[index] == 0:
                 result += 1
                 index += 1
                 if index >= answers_len:
                     break
             else:
                 result += answers[index] + 1
                 this_answer = answers[index]
                 index += 1
                 if index >= answers_len:
                     break
                 # skip at most answers[index] following answers
                 for _ in range(this_answer):
                     if answers[index] == this_answer:
                         index += 1
                         if index >= answers_len:
                             break
         return result

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         countArr = {}
         
         for i in answers:
             if i not in countArr.keys():
                 countArr[i] = 1
             else:
                 countArr[i] += 1
         
         minColors = 0
         for i in countArr.keys():
             minColors += math.ceil(countArr[i] / (i+1))*(i+1)
 
         
         return minColors

import math
 class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         
         colorGroup = collections.defaultdict(int)
         for answer in answers:
             colorGroup[answer] += 1
         toReturn = 0
         for key in colorGroup:
             claimedBuddies, claimer = key, colorGroup[key]
             ## print(claimedBuddies)
             ## print(claimer)
             toReturn += math.ceil(claimer/(claimedBuddies+1))*(claimedBuddies+1)
             ## print(toReturn)
             ## print()
         return toReturn

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         answers = sorted(answers)
         j = 0
         sum = 0
         while (answers[0] == 0):
             answers.pop(0)
             sum = sum + 1
         
         size = len(answers)
     
         #print(answers)
         while(j < size):
             #print(j)
             val = answers[j]
             inc = 0
             while (j < size and val == answers[j] and inc < val+1):
                 inc = inc + 1
                 j = j+1
             #print("adding value", val+1, j)
             sum = sum + val + 1
             
         
         return sum

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         total = 0
         d = collections.defaultdict(int)
         for ans in answers:
             d[ans] += 1
         for k, v in d.items():
             total += math.ceil(v/(k+1)) * (k+1)
         return total

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         counter = [0 for i in range(1000)]
         for i in answers:
             counter[i] += 1
         num = 0
         for k, v in enumerate(counter):
             d, m = divmod(v, k + 1)
             if d > 0:
                 num += (k + 1) * d
             if m > 0:
                 num += k + 1
         return num
             


class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         dic = dict()
         for answer in answers:
             if answer in dic:
                 dic[answer] += 1
             else:
                 dic[answer] = 1
         ans = 0
         for answer in dic:
             ans += math.ceil(dic[answer] / (answer + 1)) * (answer + 1)
         return ans

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         if answers==[]:
             return 0
         d={}
         for n in answers:
             if n in d:
                 d[n]+=1
             else:
                 d[n]=1
         total=0
         # 想清楚各种可能的边界情况
         for n in d:
             if d[n]%(n+1)==0:
                 total+=d[n]
             else:
                 total+=((d[n]//(n+1))+1)*(n+1)
                 
         return total

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         N = max(answers)
         
         bincount = [0] * (N + 1)
         for a in answers:
             bincount[a] += 1
             
         min_number_rabbits = 0
         for i in range(N + 1):
             if bincount[i] == 0:
                 continue
             group_size = i + 1
             nb_groups = math.ceil(bincount[i] / group_size)
             min_number_rabbits += nb_groups * group_size
             
         return min_number_rabbits

class Solution:
     def numRabbits(self, answers):
         """
         :type answers: List[int]
         :rtype: int
         """
         return sum( count + (-count)%(i+1)  for i, count in collections.Counter(answers).items())