Give a decimal number, such as 123. Need to figure out all smaller numbers lesser than 123 made up by 1 and 0 composed of decimal numbers such as 111, 110, 101, 100, 11, 10, 1, 0.

I am thinking of below recursive solution:

a. If the first number is 1 then we can append 0 or 1 to it. Vice versa is true for 0 if it is the first number.

b. In every step check the formed number if it is lesser than the given number. If it is greater than given number then abandon that path.

This way we can find all combinations. However, would this solution be optimal or there is some hidden mathematical logic to this problem?

  • $\begingroup$ I deleted my answer because it was incomplete. If a digit in the original number is $\geq 2$ anything to the right of it goes. A similar technique can be applied but it's a bit more annoying to explain. $\endgroup$ – orlp Feb 8 '18 at 18:02
  • $\begingroup$ It is optimal because you need to output all numbers, hence the complexity is bounded by the number of such numbers, and your algorithm already achieves this bound. $\endgroup$ – xskxzr Feb 9 '18 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.