Problem Statement
There is nothing more beautiful than just an integer number.
You are given integers a, b and c. Write each of them down in decimal notation with no leading zeros. The following operations can be performed on each of the written numbers:
- Insert a single digit at any position of the number (possibly at the beginning or at the end).
- Delete a single digit from the number.
- Replace a single digit in the number with some other digit.
An operation can only be performed if it results in a positive number with at least one digit and no leading zeros.
Each operation has an associated cost - insCost, delCost and repCost, respectively. Return the minimal possible total cost of operations needed to satisfy the equality a+b=c.
Definition
- Class:
- TheSum
- Method:
- minCost
- Parameters:
- int, int, int, int, int, int
- Returns:
- int
- Method signature:
- int minCost(int a, int b, int c, int insCost, int delCost, int repCost)
- (be sure your method is public)
Constraints
- a, b, and c will each be between 1 and 1,000,000,000, inclusive.
- insCost, delCost and repCost will each be between 0 and 1,000,000, inclusive.
Examples
44
77
11
1
1
1
Returns: 1
We just need to insert the digit 2 between the two 1's.
44
77
11
4
4
1
Returns: 2
This is the same situation as above, but with different costs. This time, the insert and delete operations are much more expensive, and it is cheaper to make two replacements instead. For example, we can turn the numbers into 44+17=61 for a total cost of 2.
100
100
10000
1000000
1000000
0
Returns: 1000000
Every possible way requires at least one insert or delete operation.
23456765
19876
927547301
7744
9876
9977
Returns: 48697
5
69
35
84
44
63
Returns: 126
61
81
29
81
73
31
Returns: 93
11
1
7
65
68
37
Returns: 102
757148
851001
413357
0
0
1
Returns: 0
749388
890852
766291
0
0
0
Returns: 0
615545
51437
289611
0
0
0
Returns: 0
16434
544291
447134
0
0
1
Returns: 0
41605
221269
909135
1
1
0
Returns: 0
379061
873981
670529
0
0
0
Returns: 0
923811
79501
701607
0
1
0
Returns: 0
71041
629217
496749
0
0
0
Returns: 0
757148
167851001
301413357
970788
597709
567065
Returns: 3969455
391749388
4890852
35766291
239546
37691
597006
Returns: 376910
3615545
326051437
392289611
341404
427628
215491
Returns: 1418859
675016434
168544291
683447134
89276
426790
752135
Returns: 714208
194041605
706221269
69909135
655526
970659
417541
Returns: 3578313
37379061
40873981
8670529
835600
290636
351377
Returns: 1804557
106923811
374079501
466701607
546278
776620
571656
Returns: 3303046
222071041
36629217
366496749
645867
839920
255787
Returns: 1790509
33557677
379268590
150378796
583325
450495
230930
Returns: 1968905
709031779
144328646
513494529
547794
997805
161580
Returns: 1131060
318773941
170724397
553666286
402602
581564
452469
Returns: 2917948
368026285
47903381
939151438
145155
919970
159111
Returns: 1030041
133145006
314295423
450219949
203052
402822
733906
Returns: 1215030
29331901
31051111
110710191
313521
695545
511284
Returns: 2078889
87708701
317333277
103301481
400406
445618
550831
Returns: 2688497
100757147
267851000
401413356
971125
598369
567226
Returns: 3403356
491749387
104890851
135766290
239573
38165
597007
Returns: 457980
103615544
426051436
492289610
341523
427799
215529
Returns: 1545162
775016433
268544290
783447133
90227
426873
752252
Returns: 631589
294041604
806221268
269909133
655784
970744
417563
Returns: 3996288
137379060
140873980
108670528
835681
291073
352031
Returns: 1868354
206923810
474079500
566701606
546365
776868
572137
Returns: 2731825
1000000000
1000000000
1000000000
0
0
0
Returns: 0
1
10000
100000000
0
1
1
Returns: 0
1
10000
100000
100
100
1
Returns: 5
7148
851001
301413357
0
0
1
Returns: 0
9388
890852
35766291
0
0
2
Returns: 0
5545
51437
392289611
2
2
0
Returns: 6
6434
544291
683447134
2
0
3
Returns: 0
8
167851001
3357
0
2
1
Returns: 0
8
4890852
6291
0
0
0
Returns: 0
5
326051437
9611
0
0
0
Returns: 0
4
168544291
7134
0
0
0
Returns: 0
5
706221269
9135
0
0
1
Returns: 0
1
40873981
529
2
1
0
Returns: 5
757148
1
7
0
0
1
Returns: 0
91749388
852
1
0
0
0
Returns: 0
3615545
437
1
0
0
0
Returns: 0
75016434
291
4
0
0
1
Returns: 0
757148
167851001
1
0
0
0
Returns: 0
391749388
4890852
1
0
0
0
Returns: 0
3615545
326051437
1
0
0
0
Returns: 0
675016434
168544291
1
0
0
0
Returns: 0
194041605
706221269
1
0
0
0
Returns: 0
37379061
40873981
1
0
0
0
Returns: 0
170204923
96336140
6100256
979139
8
553
Returns: 96
151796637
64399928
727228303
9
1
57838
Returns: 13
96421539
381320822
26242885
4016
997
75628
Returns: 11964
634967925
281126025
560586332
9
3
88847
Returns: 36
37003628
299103499
48804422
396
197
99535
Returns: 2169
931654
907023
87463378
0
673277
9905
Returns: 0
170997261
129289090
414041645
42873
6183
696243
Returns: 80379
151969068
6207535
315107787
9213
2605
723182
Returns: 31260
159373369
821294922
503935146
4935
2385
730277
Returns: 28620
700180466
946855325
802263555
67885
7498
23075
Returns: 113051
745444484
614713473
62523403
46273
8152
169924
Returns: 130432
700776847
396943122
9635533
44947
9262
28478
Returns: 148192
98073218
89851356
535901892
181
101
56020
Returns: 1149
721913117
16263
492078980
0
902929
0
Returns: 0
76013338
565764895
440924157
1
1
56670
Returns: 9
75535472
91636867
388853115
511
2257
72846
Returns: 4599
78362544
577042539
6133347
277
32796
994252
Returns: 2770
11206909
49705268
930129862
896
491
8888
Returns: 5806
10
10
10
100
1
100
Returns: 100