C++で数値を6で割り切れるようにするために削除すべき桁の位置を出力する方法

この問題では、与えられた数値から1桁を削除し、削除後にできる新しい数値が6で割り切れるようにします。そして、削除すべき桁の位置を出力します。

概念をより深く理解するために、例を見てみましょう。

入力 : 1324
出力 : 4

説明 − 4桁目を削除すると「132」が得られ、これは6で割り切れます。

つまり、数値が与えられたとき、6で割り切れるようにするために削除すべき桁の位置を返す必要があります。

この問題を解くために、ロジックを組み立てていきます。その際、「ある数が2と3の両方で割り切れるならば、その数は6で割り切れる」という性質を利用します。

桁を削除した後にできる新しい数値について、6で割り切れるかどうか(つまり2と3の両方で割り切れるかどうか)を判定します。

アプローチ

数値の性質に基づいて、ある桁を削除してできる数が6で割り切れるかどうかを判定できます。数値の最後の桁に着目すると、次の2つの場合に分けられます。

最後の桁が奇数の場合

最後の桁が奇数である場合、削除できるのは最後の桁だけです。削除後の新しい数値が6で割り切れるのは、新しい末尾となる桁(元の数の最後から2番目の桁)が偶数であり、かつ残りの桁の合計が3で割り切れる場合のみです。それ以外の場合、解は存在しません。

最後の桁が偶数の場合

最後の桁が偶数である場合、数値を3で割った余りを求め、その値に基づいて削除できる桁を特定します。

数値を3で割ると、余りによって次の3つの場合に分けられます。

余りが1の場合 − 1、4、7のいずれかの桁を削除できます。削除できる桁が複数ある場合は、削除後にできる数が最大になるように桁を選びます。

余りが2の場合 − 2、5、8のいずれかの桁を削除できます。削除できる桁が複数ある場合は、削除後にできる数が最大になるように桁を選びます。

余りが0の場合 − 3、6、9のいずれかの桁を削除できます。削除できる桁が複数ある場合は、削除後にできる数が最大になるように桁を選びます。

それでは、このロジックに基づいていくつかの例を解いて、望ましい出力を確認してみましょう。

最後の桁が奇数の場合

1. 34241341

この場合、削除できるのは最後の位置にある「1」だけです。削除後の数は「3424134」となり、これは6で割り切れます。したがって、削除した「1」の位置である「8」を返します。

2. 3214241

この場合も、削除できるのは最後の位置にある「1」だけですが、削除後の数は「321424」となり、6で割り切れません。したがって、「-1」を返します。

最後の桁が偶数の場合

1. 8097860

この場合、数値を3で割った余りは2になります。余りが2であれば、数値から「2」「5」「8」のいずれかを削除できます。この数には「8」が1桁目と5桁目の2か所にあるため、どちらかを削除できます。1桁目の「8」を削除するとより小さな数になってしまうため、5桁目の「8」を削除します。削除後の新しい数は「809760」となり、これは6で割り切れます。したがって、「5」を返します。

実装例

このロジックに基づいて、問題を解くプログラムを作成してみましょう。

#include <bits/stdc++.h>
using namespace std;
void isDivisibleBy6(string num){
    int n = num.length();
    int a[n];
    int sum = 0;
    for (int i = 0; i < n; i++) {
       a[i] = num[i] - '0';
       sum += a[i];
    }
    if (a[n - 1] % 2){
       if ( (a[n - 2] % 2 != 0) || (sum - a[n - 1]) % 3 != 0) {
          cout << "-1" << endl;
       }
       else {
          cout << n << endl;
       }
    }
    else {
       int re = sum % 3;
       int del = -1;
       int flag = 0;
       for (int i = 0; i < n - 1; i++) {
          if ((a[i]) % 3 == re) {
             if (a[i + 1] > a[i]) {
                del = i;
                flag = 1;
                break;
             }
             else {
                del = i;
             }
          }
       }
       if (flag == 0) {
          if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
             del = n - 1;
       }
       if (del == -1)
          cout << -1 << endl;
       else {
          cout << del + 1 << endl;
       }
    }
}
int main(){
    string number = "343224152";
    isDivisibleBy6(number);
    return 0;
}

出力

5