001package net.n1da.dev.euler;
002
003import net.n1da.dev.euler.core.*;
004import net.n1da.dev.euler.helper.*;
005
006/**
007 * Solution for problem 53
008 * "<strong>Combinatoric selections</strong>"
009 * completed on Tue, 16 Aug 2016, 17:43.
010 * 
011 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
012 * @since 14.08.2016 20:28:56
013 * 
014 * @see <a href="https://projecteuler.net/problem=53" target="_blank">Problem @ Project Euler</a>
015 * @see <a href="http://n1da.net/specials/projekt-euler/problem-53-kombinatorische-auswahl" target="_top">Solution @ Ni-Da-Net</a>
016 */
017public class PE0053 extends Problem {
018
019        /**
020         * A simple constructor to set {@link Problem#number number}
021         * and {@link Problem#title title}.
022         */
023        public PE0053() {
024                super( 53, "Combinatoric selections" );
025        }
026
027        /**
028         * Tries to find the smallest r from both sides, 1 to n and n to 1, that leads to
029         * a combination greater than one million. n runs from one to one-hundred itself.
030         * 
031         * @return the number of combinations that leads to more than one million
032         */
033        @Override
034        public String solve() {
035                
036                long border = 1000000L;
037                int count = 0, r, rl, ru;
038                
039                for( int n = 1; n <= 100; n++ ) {
040
041                        r = 1;
042                        while( ( r < n / 2 ) && ( combi( n, r ) < border ) ) {
043                                r++;
044                        }
045                        rl = r;
046                        
047                        r = n;
048                        while( ( r > n / 2 ) && ( combi( n, r ) < border ) ) {
049                                r--;
050                        }
051                        ru = r;
052                        
053                        if( ru > rl ) {
054                                IO.debugln( "found " + ( ru - rl + 1 ) + " combis for n = " + n );
055                                count += ( ru - rl + 1 );
056                        }
057                }
058                
059                return IO.i2s( count );
060        }
061
062        /**
063         * Calculates the number of combinations that are possible by
064         * selecting r elements out of a n-size set of elements.
065         * 
066         * @param n the number of elements
067         * @param r the size of the subset of elements
068         * @return the number of combinations
069         */
070        private long combi( int n, int r ) {
071                long result = 1;
072                
073                for( int i = n; i > 0; i-- ) {
074                        if( i > r ) {
075                                result *= i;
076                        }
077                        if( i <= ( n - r ) ) {
078                                result /= i;
079                        }
080                }
081                
082                return result;
083        }
084}