001package net.n1da.dev.euler.helper;
002
003import java.util.Arrays;
004
005/**
006 * A class for large numbers without any limits using an array of digits
007 * as internal storage.
008 * 
009 * @author <a href="mailto:nico@danneberg.de">Nico Danneberg</a>
010 * @since 23.04.2015 22:46:14
011 */
012public class LargeNumber implements Comparable< LargeNumber > {
013
014        /**
015         * A memory that provides the factorial for the numbers from 0 to 9.
016         * Within method {@link #sumOfDigitFactorials()} is saves some calculation time.
017         * 
018         * @see #sumOfDigitFactorials()
019         */
020        private static final int[] FACTORIALS = new int[]{
021                1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880
022        };
023                        
024        /**
025         * The storage of the digits.
026         */
027        private int[] data;
028        
029        /**
030         * Sometimes not all digits of a large number are necessary. Due to performance
031         * reasons the current number is never greater than {@link #max} digits.
032         */
033        private int max;
034        
035        /**
036         * Creates a large number with value zero.
037         */
038        public LargeNumber() {
039                this( 0 );
040        }
041        
042        /**
043         * Creates a large number with the given value and no restrictions to
044         * the {@link #max maximum} number of digits.
045         * 
046         * @param value the initial value
047         */
048        public LargeNumber( int value ) {
049                this( value, -1 );
050        }
051        
052        /**
053         * Creates a large number with the given value that will never has more
054         * digits than the given maximum.
055         * 
056         * @param value the initial value
057         * @param max the maximum number of digits this number will every have
058         */
059        public LargeNumber( int value, int max ) {
060                this.max = max;
061                
062                int len = ( max > -1 ) ? max : Integer.toString( value ).length();
063                data = new int[ len ];
064                
065                if( value == 0 ) {
066                        data[ 0 ] = 0;
067                } else {
068                        int i=0;
069                        while( value > 0 && i < len ) {
070                                data[ i++ ] = value % 10;
071                                value /= 10;
072                        }
073                }
074        }
075        
076        /**
077         * Creates a large number with the internal value of the given array.
078         * 
079         * @param digits the initial value
080         */
081        public LargeNumber( Integer[] digits ) {
082                this.max = -1;
083                data = new int[ digits.length ];
084                for( int i=0; i<digits.length; i++ ) {
085                        data[ digits.length - 1 - i ] = digits[ i ];
086                }
087        }
088        
089        /**
090         * Adds the given number to the current objects and returns the sum
091         * of both.
092         * 
093         * @param num another {@link #LargeNumber()}
094         * @return the sum
095         */
096        public LargeNumber add( LargeNumber num ) {
097                LargeNumber res = new LargeNumber( 0, Math.max( max, num.max ) );
098                
099                int max = Math.max( data.length, num.data.length );
100                res.data = new int[ max + 1 ];
101                
102                int a, b, mod=0, sum;
103                
104                for( int i=0; i<max; i++ ) {
105                        a = ( i<data.length ) ? data[ i ] : 0;
106                        b = ( i<num.data.length ) ? num.data[ i ] : 0;
107                        sum = a + b + mod;
108                        res.data[ i ] = sum % 10;
109                        mod = sum / 10;                 
110                }
111                
112                res.data[ max ] = mod;
113                res.trim();
114                
115                return res;
116        }
117        
118        /**
119         * Clones the current number to return a new {@link LargeNumber}
120         * with the same values in its {@link #data}.
121         * 
122         * @return a new {@link LargeNumber}
123         */
124        @Override
125        public LargeNumber clone() {
126                LargeNumber res = new LargeNumber();
127                res.data = this.data.clone();
128                res.max = this.max;
129                return res;
130        };
131
132        /**
133         * Compares this object with the given one.
134         * 
135         * @param num the number to compare with
136         * @return 1 if this object if greater that, -1 if it's lower than, and 0 it it's equal to the given number
137         */
138        @Override
139        public int compareTo( LargeNumber num ) {
140
141                if( data.length > num.data.length )
142                        return 1;
143                
144                if( data.length < num.data.length )
145                        return -1;
146                
147                for( int i=data.length-1; i>=0; i-- ) {
148                        if( data[ i ] > num.data[ i ] )
149                                return 1;
150
151                        if( data[ i ] < num.data[ i ] )
152                                return -1;
153                }
154                
155                return 0;
156        }
157        
158        /**
159         * Checks, if the given object is equal to the current number.
160         * 
161         * @param o the object to test the value against the current number
162         * @return true, if the given object is a {@link LargeNumber} with the same values in {@link #data}
163         */
164        @Override
165        public boolean equals( Object o ) {
166
167                if( o instanceof LargeNumber ) {
168                        LargeNumber n = ( LargeNumber ) o;
169                        
170                        if( n.data.length != data.length )
171                                return false;
172                        
173                        for( int i=0; i<data.length; i++ )
174                                if( data[ i ] != n.data[ i ] )
175                                        return false;
176                        
177                        return true;
178                }
179                
180                return false;
181        }
182        
183        /**
184         * Reads and returns a digit at the wanted position.
185         * 
186         * @param pos the position to read the digit from
187         * @return a digit at the given position
188         */
189        public int getDigit( int pos ) throws ArrayIndexOutOfBoundsException {
190                if( ( pos <= -1 ) || ( pos >= data.length ) ) {
191                        throw new ArrayIndexOutOfBoundsException();
192                }
193                
194                return data[ pos ];
195        }
196        
197        /**
198         * Reads the length of {@link #data} to get the number of digits in
199         * this large number.
200         * 
201         * @return the length (count of digits) of the large number
202         */
203        public int getLength() {
204                return data.length;
205        }
206        
207        /**
208         * Just sorts the values in {@link #data}.
209         * 
210         * @return A new {@link LargeNumber} with sorted digits
211         */
212        public LargeNumber getWithSortedDigits() {
213                LargeNumber ret = clone();
214                Arrays.sort( ret.data );
215                return ret;
216        }
217        
218        /**
219         * It calculates and returns the hashcode of this object.
220         * 
221         * @return the hascode of the string representation of this object
222         * @see #toString()
223         * @see java.lang.String#hashCode()
224         */
225        @Override
226        public int hashCode() {
227                return toString().hashCode();
228        }
229        
230        /**
231         * Checks if a large number is palindromic.
232         * 
233         * @return true if the number is a palindrom
234         */
235        public boolean isPalindromic() {
236                int center = data.length / 2;
237                for( int pos = 0; pos < center; pos++ ) {
238                        if( data[ pos ] != data[ data.length - pos - 1 ] ) {
239                                return false;
240                        }
241                }
242                return true;
243        }
244        
245        /**
246         * Checks if the given number is a permutation of the current object.
247         * 
248         * @param num the number to be checked
249         * @return true if every digit of {@link #data} exists exactly once in both numbers
250         */
251        public boolean isPermutationOf( LargeNumber num ) {
252                return num.getWithSortedDigits().equals( this.getWithSortedDigits() );
253        }
254        
255        /**
256         * Multiplies the current number with the given integer value.
257         * 
258         * @param n the number to multiply with
259         * @return the product of the given integer and the current object
260         */
261        public LargeNumber mult( int n ) {
262                LargeNumber res = this.clone(), cur = this.clone();
263                
264                if( n < 1 )
265                        return new LargeNumber();
266                
267                if( n > 1 ) 
268                        for( int i=1; i<n; i++ ) {
269                                res = res.add( cur );
270                        }
271                
272                return res;
273        }
274
275        /**
276         * Multiplies the current number with the given {@link LargeNumber}.
277         * 
278         * @param n the number to multiply with
279         * @return the product of the both {@link LargeNumber}s
280         */
281        public LargeNumber mult( LargeNumber n ) {
282                LargeNumber res = new LargeNumber();
283                
284                for( int i=n.data.length-1; i>=0; i-- ) {
285                        res = res.mult( 10 );
286                        LargeNumber temp = this.mult( n.data[ i ] );
287                        res = res.add( temp );
288                }
289                
290                return res;
291        }
292        
293        /**
294         * Parses the given string and creates a new {@link #LargeNumber()}
295         * with this value.
296         * 
297         * @param line the string to parse
298         * @return a new large number
299         */
300        public static LargeNumber parse( String line ) {
301                LargeNumber res = new LargeNumber();
302                int len = line.length();
303                res.data = new int[ len ];
304                
305                int pos = len - 1;
306                for( byte b : line.getBytes() )
307                        if( ( b >= 48 ) && ( b <= 57 ) )
308                                res.data[ pos-- ] = b - 48;
309                
310                return res;
311        }
312        
313        /**
314         * Calculates the power of the current number by the given integer value.
315         * 
316         * @param exp the exponent to power with
317         * @return the power of the current number by the given integer value
318         */
319        public LargeNumber pow( int exp ) {
320                LargeNumber res = this.clone();
321                
322                if( exp == 0 )
323                        return new LargeNumber( 1 );
324                
325                if( exp > 0 ) {
326                        while( exp > 1 ) {
327                                res = res.mult( this.clone() );
328                                exp--;
329                        }
330                }
331                
332                return res;
333        }
334        
335
336        /**
337         * Replaces every occurrence of a wanted digit by another
338         * given digit.
339         * 
340         * @param search the digit to be replaced
341         * @param replace the new digit
342         * @return a new large number with replaced digits
343         */
344        public LargeNumber replaceDigit( int search, int replace ) {
345                LargeNumber result = new LargeNumber();
346                result.data = new int[ data.length ];
347                
348                for( int i = 0; i < data.length; i++ ) {
349                        result.data[ i ] = ( data[ i ] == search ) ? replace : data[ i ];
350                }
351                
352                return result;
353        }
354        
355        /**
356         * Creates a copy of this large number that has reverse ordered digits.
357         * 
358         * @return a new large number with reverse ordered digits
359         */
360        public LargeNumber reverse() {
361                LargeNumber result = new LargeNumber();
362                result.data = new int[ data.length ];
363                
364                for( int i = 0; i < data.length; i++ ) {
365                        result.data[ i ] = data[ data.length - i - 1 ];
366                }
367                
368                return result;
369        }
370        
371        /**
372         * Subtracts the given number from the current objects and returns the difference
373         * of both.
374         * 
375         * @param num another {@link #LargeNumber()}
376         * @return the difference
377         */
378        public LargeNumber sub( LargeNumber num ) {
379                
380                if( this.compareTo( num ) == 0 ) {
381                        return new LargeNumber();
382                }
383                
384                if( this.compareTo( num ) == -1 ) {
385                        return num.sub( this );
386                }
387                
388        
389                LargeNumber res = new LargeNumber( 0, Math.max( max, num.max ) );
390                
391                int max = Math.max( data.length, num.data.length );
392                res.data = new int[ max + 1 ];
393                
394                int a, b, mod=0, diff;
395                
396                for( int i=0; i<max; i++ ) {
397                        a = ( i<data.length ) ? data[ i ] : 0;
398                        b = ( i<num.data.length ) ? num.data[ i ] : 0;
399                        diff = a - b - mod;
400                        res.data[ i ] = ( diff < 0 ) ? 10 + diff : diff;
401                        mod = ( diff < 0 ) ? 1 : 0;
402                }
403                
404                res.trim();
405                
406                return res;
407        }
408
409        /**
410         * Calculates the sum of all digits of this {@link LargeNumber}.
411         * 
412         * @return the cross total
413         */
414        public LargeNumber sumOfDigits() {
415                return sumOfDigitPowers( 1 );
416        }
417        
418        /**
419         * Calculates the sum of the factorials of all digits of this {@link LargeNumber}.
420         * If this number is <code>n = 123</code> this method will return
421         * <code>s = 1!+2!+3! = 1+2+6 = 9</code>!
422         * 
423         * @return the cross total
424         */
425        public LargeNumber sumOfDigitFactorials() {
426                LargeNumber res = new LargeNumber();
427                
428                for( int digit : data ) {
429                        res = res.add( new LargeNumber( FACTORIALS[ digit ] ) );
430                }
431                
432                return res;
433        }
434
435        /**
436         * Calculates the sum of the power of all digits of this {@link LargeNumber}.
437         * If this number is <code>n = 123</code> this method will return
438         * <code>s = 1<sup>2</sup>+2<sup>2</sup>+3<sup>2</sup></code> with given parameter <code>exp = 2</code>!
439         * 
440         * @param exp the exponent to calculate the power with
441         * @return the cross total
442         */
443        public LargeNumber sumOfDigitPowers( int exp ) {
444                LargeNumber res = new LargeNumber();
445                
446                for( int digit : data ) {
447                        LargeNumber cur = new LargeNumber( digit );
448                        res = res.add( cur.pow( exp ) );
449                }
450                
451                return res;
452        }
453        
454        /**
455         * Return the current number as {@link java.lang.String string}.
456         * 
457         * @return the current number as {@link java.lang.String string}
458         */
459        @Override
460        public String toString() {
461                String res = "";
462                
463                if( data.length == 0 ) {
464                        res = "0";
465                } else {
466                        for( int i=data.length-1; i>=0; i-- )
467                                res += Integer.toString( data[ i ] );
468                }
469
470                return res;
471        }
472
473        /**
474         * Deletes all leading zeros from the current number.
475         */
476        public void trim() {
477
478                int cnt = 0;
479                for( int i=data.length-1; i>=0; i-- )
480                        if( data[ i ] == 0 )
481                                cnt++;
482                        else
483                                i=-1;
484                
485                int len = ( ( max > -1 ) && ( max < data.length - cnt ) ) ? max : data.length - cnt;
486                
487                int[] tmp = new int[ len ];
488                for( int i=0; i<tmp.length; i++ )
489                        tmp[ i ] = data[ i ];
490                        
491                data = tmp;
492        }
493}