Need some unit tests to cover extreme large numbers (thousands of digits) to make sure of no overflow happens.


  • 0
    T

    my solution passed LEECODE tests. But let my solutions fails (overflow) when I multiply two numbers with thousands of digits.

    It seems it need some unit tests to cover extreme large numbers (thousands of digits) to make sure of no overflow happens.


  • 0

    Could you please post your code and also an example large test case that demonstrate the problem? Thanks.


  • 0
    T

    without following lines, my solution will pass leecode test cases, but fail on extren large numbers

                if ( arraySum[index1+index2] >= UNIT_MAX_VALUE ) {
                    long carryOver = arraySum[index1+index2]/UNIT_MAX_VALUE;
                    arraySum[index1+index2] = arraySum[index1+index2] % UNIT_MAX_VALUE;
                    arraySum[index1+index2+1] += carryOver;
                }
    

  • 0
    T

    my code:

    private static final int UNIT_SIZE = 9;
    private static final long UNIT_MAX_VALUE = 1_000_000_000;
    
    public long[] strToLong(String num) {
        long[] arrayNum = new long[(num.length()+UNIT_SIZE-1)/UNIT_SIZE];
    
        int index = 0;
        for ( int endPosition = num.length(); endPosition > 0; endPosition -= UNIT_SIZE) {
            int startPosition = endPosition - UNIT_SIZE;
            if ( startPosition < 0 )
                startPosition = 0;
            String tmp = num.substring(startPosition, endPosition);
            arrayNum[index++] = Long.parseLong(tmp);
        }
    
        return arrayNum;
    }
    
    public String multiply(String num1, String num2) {
        long[] arrayNum1 = strToLong(num1);
        long[] arrayNum2 = strToLong(num2);
        long[] arraySum = new long[arrayNum1.length+arrayNum2.length];
        for ( int index1 = 0; index1<arrayNum1.length; index1++) {
            for ( int index2 = 0; index2<arrayNum2.length; index2++) {
                arraySum[index1+index2] += arrayNum1[index1] * arrayNum2[index2];
                if ( arraySum[index1+index2] >= UNIT_MAX_VALUE ) {
                    long carryOver = arraySum[index1+index2]/UNIT_MAX_VALUE;
                    arraySum[index1+index2] = arraySum[index1+index2] % UNIT_MAX_VALUE;
                    arraySum[index1+index2+1] += carryOver;
                }
            }
        }
    
        long carryOver = 0;
        for ( int index=0; index<arraySum.length; index++) {
            arraySum[index] += carryOver;
            if ( arraySum[index] >= UNIT_MAX_VALUE ) {
                carryOver = arraySum[index]/UNIT_MAX_VALUE;
                arraySum[index] = arraySum[index] % UNIT_MAX_VALUE;
            }
            else {
                carryOver = 0;
            }
        }
    
        int index = arraySum.length-1;
        while (index>=0 && arraySum[index] == 0)
            index--;
    
        if ( index < 0 )
            return "0";
    
        StringBuffer sb = new StringBuffer();
    
        String tmp = String.format("%d", arraySum[index]);
        sb.append(tmp);
        index--;
    
        while (index>=0) {
            tmp = String.format("%09d", arraySum[index]);
            sb.append(tmp);
            index--;
        }
        return sb.toString();
    }
    

  • 0
    T

    large number sample (1000 digits):

        // 1000 digits * 1000 digits
        assertEquals(
                "77353738199525217326848920192771817493295432697787441886506309426911375384663836941026591809063436123273131957751195167152300886702426155870347239639099312686717601957337856474410832371594081064641683671706971497765456014901230263856469122859142323569014463414834333126563843817305841370203722607263593535478434268132452770524822131683383221349289746567878922492657007822312112396405829218354881846121732427762677326985769045788854083138473756683072711810677291309417901282849715465635477924674841454246107137432738625941051354339486869888014377118304275871396177158761023561642686764526118960063776464375497451660859524351706429613979890459893679744036533201931497044809540548254187574517887788605218021154906357809962826439518658690809162545812737645299136580132891348532064897084405467317245401361146669700642663844693635275144367648201909838364145252234428541036513377036787479407768507364864171597505871845705875537283522365541438397613723500058063078234160787247383867858945745328704267523381278125400133690086034889084364023875765936821979626181917833520492704199324875237825867148278905344897440142612317035699548419499444610608146207254036559998271588356035049327795540741961849280952093753026852390937562839148571612367351970609224242398777007574955787271559767413458997537695515862718887941516307569668816352155048898271704378508028434084412644126821848514157729916034497017892335796684991447389566001932545827678000618329854426232827257556110733160697015864984222291255485729879337147866323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625",
                solution.multiply(
                        "278125400133690086034889084364023875765936821979626181917833520492704199324875237825867148278905344897440142612317035699548419499444610608146207254036559998271588356035049327795540741961849280952093753026852390937562839148571612367351970609224242398777007574955787271559767413458997537695515862718887941516307569668816352155048898271704378508028434084412644126821848514157729916034497017892335796684991447389566001932545827678000618329854426232827257556110733160697015864984222291255485729879337147866323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625",
                        "278125400133690086034889084364023875765936821979626181917833520492704199324875237825867148278905344897440142612317035699548419499444610608146207254036559998271588356035049327795540741961849280952093753026852390937562839148571612367351970609224242398777007574955787271559767413458997537695515862718887941516307569668816352155048898271704378508028434084412644126821848514157729916034497017892335796684991447389566001932545827678000618329854426232827257556110733160697015864984222291255485729879337147866323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625"));
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.