diff options
author | Jack Sangdahl <[email protected]> | 2025-04-19 18:13:54 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-19 18:13:54 -0600 |
commit | fef03eaef98cc479f58c4e1dd4619db665f97e8f (patch) | |
tree | 4ec9c4ac9840ffdc66464ad3cb72325e587cc9d9 | |
parent | 2e01488b5f45d49e16b116f2b0c858c69bd0dd26 (diff) | |
download | leetcode-fef03eaef98cc479f58c4e1dd4619db665f97e8f.tar.gz leetcode-fef03eaef98cc479f58c4e1dd4619db665f97e8f.zip |
781. rabbits in forest
-rw-r--r-- | rabbits_in_forest.c | 36 | ||||
-rw-r--r-- | rabbits_in_forest.py | 30 |
2 files changed, 66 insertions, 0 deletions
diff --git a/rabbits_in_forest.c b/rabbits_in_forest.c new file mode 100644 index 0000000..caf618f --- /dev/null +++ b/rabbits_in_forest.c @@ -0,0 +1,36 @@ +// 781. Rabbits in Forest +#include "leetcode.h" + +/* + * there is a forest with an unknown number of rabbits. we asked 'n' rabbits + * "how many rabbithave the same colour as you?" and collected the answers in an + * integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit. + * given the array 'answers', return the minimum number of rabbits that could be + * in the forest. + */ + +int numRabbits(int *answers, int answersSize) { + int ans = 0; + for (int i = 0; i < answersSize - 1; i++) { + int freq = 0; + if (answers[i] != -1 && answers[i]) + for (int j = i + 1; j < answersSize; j++) { + if (answers[i] == answers[j]) { + answers[j] = -1; + freq++; + } + if (freq == answers[i]) + break; + } + } + for (int i = 0; i < answersSize; i++) + if (answers[i] != -1) + ans += (answers[i] + 1); + return ans; +} + +int main() { + int a1[] = {1, 1, 2}, a2[] = {10, 10, 10}; + printf("%d\n", numRabbits(a1, ARRAY_SIZE(a1))); // expect: 5 + printf("%d\n", numRabbits(a2, ARRAY_SIZE(a2))); // expect: 11 +} diff --git a/rabbits_in_forest.py b/rabbits_in_forest.py new file mode 100644 index 0000000..7d91e99 --- /dev/null +++ b/rabbits_in_forest.py @@ -0,0 +1,30 @@ +# 781. Rabbits in Forest +from collections import Counter + +""" +there is a forest with an unknown number of rabbits. we asked 'n' rabbits +"how many rabbithave the same colour as you?" and collected the answers in an +integer array 'answers' where 'answers[i]' is the answer of the i'th rabbit. +given the array 'answers', return the minimum number of rabbits that could be +in the forest. +""" + + +class Solution(object): + def numRabbits(self, answers): + """ + :type answers: List[int] + :rtype: int + """ + ans, freq = 0, Counter() + for i in answers: + if freq[i] % (i + 1) == 0: + ans += i + 1 + freq[i] += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.numRabbits(answers=[1, 1, 2])) + print(obj.numRabbits(answers=[10, 10, 10])) |