A traveller has less than 400 coins with him. Along the way he meets 4 vagabonds. To the first vagabond he gives 4 coins and of the remaining coins he gives 1/4 th of the coins to the same vagabond. To the second vagaond he gives 4 coins and of the remaining coins he gives 1/4 th of the coins... this goes on for the 3rd and the 4th vagabond. After he has given the coins to the 4th vagabond he has some coins still left and none of the coins are cut while distributing.
How many coins did the traveller have?
Before jumping to the solution of this puzzle lets note down some important points about this puzzle:
First lets define some class variables for constants. By defining class variables, not only will the code be readable and re-usable, it would also be flexible since at any point you can change the number of vegabonds, max allowed coins etc. The class variables would look like this:
private int NUM_VEGABOND = 4;
private int NUM_COINS_UPFRONT = 4;
private int MAX_ALLOWED_COINS = 1000;
A typical program should have smaller methods or functions with intuitive names. In this example we will be looping through number of coins starting from 1 to 400 and with each iteration there will be some conditions we will look for. Those conditions are:
Do we have more than zero coins (or atleast one coin)?
A simple method for this would look like this. (num is the input of number of coins in the current iteration)
private boolean hasMoreThanZeroCoins(int num)
{
return num > 0;
}
Do we have enough coins to divide with?
At any point the number of coins should be greater than 4 (num of vegabond), since we cannot cut the coins
private boolean hasEnoughCoins(int num)
{
return num > NUM_VEGABOND;
}
Are the coins exactly divisible?
At any point the number of coins should be exactly divisible by 4 (number of vegabonds)
private boolean isDivisable(int num)
{
return num % NUM_VEGABOND == 0;
}
The solve() method will look like this:
public void solve()
{
for (int currentNum = NUM_VEGABOND; currentNum < MAX_ALLOWED_COINS; currentNum++)
{
int remainingCoins = currentNum;
for (int currentVegabond = 0; currentVegabond <NUM_VEGABOND ; currentVegabond++)
{
remainingCoins = remainingCoins - NUM_COINS_UPFRONT;
if (hasMoreThanZeroCoins(remainingCoins) && hasEnoughCoins(remainingCoins) && isDivisable(remainingCoins) )
{
remainingCoins = remainingCoins - remainingCoins / NUM_VEGABOND;
}
else
{
remainingCoins = 0;
}
}
if (remainingCoins > 0 && remainingCoins < currentNum )
{
System.out.println("Total coins is :" + currentNum);
}
}
}
244.
When you run the program you will get the output:
Total coins is :244
When you run the program with max coins as 1000, you will get more than one answer:
Total coins is :244
Total coins is :500
Total coins is :756