We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Sherlock and The Beast
  5. Discussions

Sherlock and The Beast

  • isloat
     + 1 comment

    This post is not meant to provide a code answer (there are plenty of other posts that do that) but to explain how beginners should intellectually approach this problem and others like it.

    By examining the specifications and eliminating the irrelevant ones, you can figure out how to solve the problem. You also reduce the potential of confusing yourself, becoming sidetracked onto solving something else, or overcomplicating the problem and your solution. 

Specifications:
1. The number must be of length N.
2. The number must contain only '3's and '5's.
3. The amount of '3's is divisible by 5.
4. The amount of '5's is divisible by 3.
5. If there are multiple acceptable matches, choose the largest one.

A. Due to #5, we recognize immediately that all '5's must come before all '3's. Therefore we can discard numbers like 53353533, for example.

B. Due to A, #3, and #4, we recognize that '3's will always come in a sequence of '33333' and '5's will always come in a sequence of '555'.

C. Due to #3 and #4, #2 is of little functional relevance. '555' is equivalent to 'XXX' and '33333' is equivalent to 'YYYYY' here, as long as all 'X's come before all 'Y's.

D. Due to A, B, C, #1, and #5, we recognize that we can use a greedy algorithm to solve this problem. Due to B, we know that 'XXX' takes absolute priority over 'YYYYY'. 'YYYYY' is only needed to "fill in" any remaining gaps. You can immediately find the closest match using 'XXX' only, then iterate downwards (remove X and add Y) until you find a valid string of exactly N length.

    From the above, you can easily derive the necessary code in any language. This type of approach is broadly applicable to many other problems, not just this one. Knowledge of algorithm design techniques will be helpful.