AtCoder Beginner Contest 176 B Problem "Multiple of 9" Explanation (Python3, C ++, Java)

This is Rute. This article is a continuation of the previous A problem </ b> commentary!

Links to each problem / explanation

A B C
ABC176 A Thisarticle!!! ABC176C

Now, I will explain the B problem </ b>.

Problem summary

Determine if $ N $ is a multiple of $ 9 $.

Constraint

・ $ 0 \ leq N \ leq 10 ^ {200000} $ ・ $ N $ is an integer

Please note that this time, the solution method is different between Python3, C ++, and Java.

Commentary

Solution 1 (for Python 3)

  • You can also solve it with Solution 2, which will be explained later. In the case of Python3, there is no limit to the number of integers that can be represented by ʻint` type </ b>, so you can AC by writing the following conditional branch! (Strictly speaking, it can handle multiple-precision integers) </ font>

{ABC176B.py}


print("Yes") if int(input())%9 == 0 else print("No")
  • The code has been shortened here, but there is no problem if you solve it without shortening it.

Solution 2 (for C ++ and Java)

Let's pay attention to this constraint. ・ $ 0 \ leq N \ leq 10 ^ {200000} $ </ font>

Yes, the range of $ N $ is up to $ 10 ^ {200000} $. Since $ 10 ^ {64} $ is a 1 immeasurable </ b>, $ 10 ^ {200000} $ is a incredibly large integer </ b>.

In C ++, such an integer cannot be represented by the ʻinttype or even thelong long inttype. </ font> (In Java this is along` type)

So everyone, let's check the nature of multiples of $ 9 $. First of all, please see this video.

The nature of multiples of 9 (source: Trivia Fountain)




The answer to multiplying 9 is always 9 when you add the numbers together </ font>

This is equivalent to if it is a multiple of $ 9 $, the sum of digits is divisible by $ 9 $ </ b>. (Similar to this is stated in the problem statement) </ font> In other words, I was able to replace it with the simple problem of determining whether the sum of digits is divisible by $ 9 $ </ b>. It takes linear time for the length of the string </ b> to find the sum of digits, but within the constraints it is in time for the execution time limit.

Below, an example of the solution in Solution 2 is shown in three languages: Python3, C ++, and Java.

Example of answer for each language (Solution 2)

Example solution in Python3

{ABC176B2.py}


N = input()
ans = 0
for i in range(len(N)):
  ans += N[i]
print("Yes") if ans%9 == 0 else print("No")
Example solution in C ++

{ABC176B2.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < s.size(); i++){
    ans = ans +  int(s.at(i))-48;
  }
  if (ans%9==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}
  • The sum of digits was calculated using the nature of the ASCII code. In ASCII code, '0' is 48 and '9' is 57, so you can convert the string to an integer by subtracting 48 from the ASCII code.
Java answer example

{ABC176B2.java}


import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String S = scan.next();
    int ans = 0;
    for (int i = S.length(); i > 0 ; i--){
      ans = ans + Integer.parseInt(S.substring(i-1,i));
    }
    if (ans % 9 == 0){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}

Recommended Posts