AtCoder Beginner Contest 169 B Problem "Multiplication 2" Explanation (Python3, C ++, Java)

AtCoder Beginner Contest 169 B I will explain the problem "Multiplication 2".

Problem URL: https://atcoder.jp/contests/abc169/tasks/abc169_b

Problem summary

A sequence of $ N $ integers ($ A_1, ..., A_N $) is given. $ A_1 × ... × A_N $, that is

\prod_{i=1}^{N} A_i

Ask for. However, if this value exceeds $ 10 ^ {18} $, output -1.

Constraint

・ $ 2 \ leq N \ leq 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ {18} $ ・ All inputs are integers

Commentary

This problem requires knowledge of multiple precision integers </ b>. If you enter the values of these sequences in ʻinttype and multiply them, <b> overflow will occur. </ b> Also, since the constraint is up to $ 10 ^ {18} $, <b> overflow will occur even if you input and multiply withlong int` type. </ b>

Therefore, we have to take some measures.

Countermeasure 1 (Sort the sequence in descending order)

Sorting in descending order allows you to sort the sequence in descending order of numbers. Sorting the sequence has the same total product </ b>, so this is a good move. After that, multiply the values in the sequence and output -1 when it exceeds </ b> $ 10 ^ {18} $ and end the process. The amount of calculation is $ O (logN) $ for sorting and $ O (N) $ for multiplication, so it is $ O (NlogN) $.

Also, if you do not finish the process, it will be TLE </ font> in some languages. The reason is simple: multiplication of multiple-precision integers takes a long time to calculate. For example, in Python3, C ++, Java, execute $ 100 × 100 $, $ 10 ^ 5 × 10 ^ 5 $, $ 10 ^ 9 × 10 ^ 9 $ multiplication, and $ 10 ^ {18} $ multiple times respectively. Let's compare the calculation time (I used the code test of AtCoder) (In Python3, I entered the value as ʻint, in C ++ as long long int, and in Java, as double` type and executed it. ( Calculation is based on the assumption that overflow will occur </ b>)

Calculation Python3 C++ Java
100×100 18ms 6ms 122ms
10^5×10^5 21ms 10ms 106ms
10^9×10^9 18ms 7ms 122ms
10^{18}×10^{18} 19ms 8ms 122ms
{10^{18}}^{100} 18ms 6ms 118ms
{10^{18}}^{10000} 585ms 8ms 113ms
{10^{18}}^{100000} 10500ms 9ms 118ms

As you can see, there is not much difference in calculation time between C ++ and Java, but with Python3, the execution time is limited due to the large number of calculations 2sec (2000ms) </ font> You can see that font> takes more calculation time.

Measure 2 (note 0)

If there is even one $ 0 $ in the sequence, the total product will naturally be $ 0 $, but if you do the same as Countermeasure 1, the sequence that includes $ 0 $ will actually output -1. Will be done. The reason is simple. This is because it is judged that the total product exceeds $ 10 ^ {18} $ due to the term with a large value that is not $ 0 $ by sorting, and it is output as -1 </ b>. This causes the WA </ font> judgment to appear in the corner case such as zero_01.txt. So, when reading a sequence, let's create a flag function that sets $ 0 $ to 1 if it exists </ b>. Then you can determine if the total product is $ 0 $ before multiplying! </ B> In Python3, you can check if the $ 0 $ term exists in ʻA.count (0)`.

Summary / answer example

In other words, the points of each language for this problem are as follows.

・ Python3 Multiplication of multiple-precision integers </ b> takes a lot of calculation time and should be avoided. ・ C ++, Java It is better to avoid calculation errors due to overflow </ b>

Below are examples of solutions in Python3, C ++, and Java.

Example solution in Python3

{ABC169.py}


N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
if A.count(0) > 0:
  print(0)
else:
  f = 0
  ans = 1
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      f += 1
      print(-1)
      break
  if f == 0:
    print(ans)
Example solution in C ++

{ABC169.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<long int> vec(n);
  for (int i = 0; i < n; i++){
    long int a;
    cin >> a;
    vec.at(i) = a;
    if(vec.at(i) == 0){
      cout << 0 << endl;
      return 0;
    }
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  long int ans = 1;
  for (int i = 0; i < n; i++){
    if (vec.at(i) > 1000000000000000000/ans){
      cout << -1 << endl;
      return 0;
    }else{
      ans *= vec.at(i);
    }
  }
  cout << ans << endl;
}
Java answer example

{ABC169.java}


import java.util.Scanner;
import java.util.Arrays;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    long [] a = new long[n];
    for (int i = 0; i < n; i++){
      a[i] = scan.nextLong();
      if (a[i] == 0){
        System.out.println(0);
        return;
      }
    }
    
    Arrays.sort(a);
    
    long ans = 1;

    for (int i = n-1; i >= 0; i--){
      if (a[i] > 1000000000000000000L/ans){
        System.out.println(-1);
        return;
      }else{
        ans *= a[i];
      }
    }
    System.out.println(ans);
  }
}

Recommended Posts