Traveler and the coins

 

Problem: 

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?

Approach:

Before jumping to the solution of this puzzle lets note down some important points about this puzzle:

• there are 4 vagabonds
• the number of coins to be given upfront is 4
• Maximum number of coins the traveller had is less than 400
• At any point when dividing the coins the total number of the coins was divisable by 4 (quarter of the remaining coins) 

Class Variables:

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:

Building Blocks:

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

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

}

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

• loop through 4 (num of vegabond) to 400 (Max coins)
  • ​for each iteration loop through 1 to 4 (number of vegabonds)
    • ​subtract 4 (num of vegabonds) from current number
    • if the remaining number is greater than 0 and has enough coins and is exactly divisble by 4 (num of vegabonds) then subract 1/4th of the remaining coins

​The solve() method will look like this:

public void solve()

Answer:

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