Hello, pranay!

If one has a stick of length , then what is the minimum number of cuts

one can make on it to have n parts of it so that at the end of day

one can give units of stick to someone?

This is a classic problem.

A traveller has a chain of seven gold links

. . and wants to stay seven days at an inn.

The inn charges one link per night.

The traveller agrees to pay one link per day.

The innkeeper does not want seven cut links.

. . He will accept the minimum number of cuts.

How should the traveller cuts the links?

- - . . . . . . . .

. .Day. .Payment. . . .Action

. . . 1 . . . . . 1 . . . . . . . Give 1

. . . 2 . . . . . 2 . . . . Give 2, take 1

. . . 3 . . . . 2+1 . . . . . Give 1

. . . 4 . . . . . 4 . . . Give 4, take 1 & 2

. . . 5 . . . . 4+1 . . . . . . Give 1

. . . 6 . . . . 4+2 . . . . Give 2, take 1

. . . 7 . . . 4+2+1 . . . . . Give 1

In general, partition into powers-of-2.

For example: .n = 100 requires 6 cuts.

. . 100 .= .1 + 2 + 4 + 8 + 16 + 32 + 37