Problem statement: Given a cage that has R rabbits and C chicken, and we know there are H heads and L legs. So find out the value of R and C (how many rabbits and how many chicken)
Math Equation to solve chicken and rabbit problem
We can express the problem using Math equations:
We know a rabbit has four legs and a chicken has two legs. Both rabbit and chicken have only 1 head (of course!). In the above equation, we have 2 unknowns R and C, and the H and L are given, and thus we can solve the equation for the unknowns.
Bruteforce Algorithm to solve Chicken and Rabbit
We can bruteforce R or C from 0 to the maximum H value, and then check if the legs are the same as L.
1 2 3 4 5 6 7 8 | def solve(heads, legs): r = 0 while r <= heads: c = heads - r if 4 * 4 + 2 * c == legs: return [r, c] r += 1 return None # can't find any valid solution |
def solve(heads, legs):
r = 0
while r <= heads:
c = heads - r
if 4 * 4 + 2 * c == legs:
return [r, c]
r += 1
return None # can't find any valid solution
There are only H possibilities and sure this can be solved by computer in no time.
Actually, we can solve the linear equation with 2 unknowns and implement the solution in O(1) constant time: Teaching Kids Programming – Linear Equation with Two Unknowns (Chicken and Rabbit Problem)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Algorithms to Check if a String is a Subsequence String of Another String
Next Post: Two Pointer with Sliding Window Algorithm to Compute the Longest Substring with At Most K Distinct Characters
