判断一个用字符串表达的数字是否可以被整除

比眉伴天荒 2024-03-26 15:03 95阅读 0赞

## 一.问题引出 ##

当一个数字很大的时候,我们常用字符串进行表达,(超过了int和long等数据类型可以存储的最大范围),但是这个时候我们该如何判断他是否可以被另一个数整除呢?

这个时候我们不妨这样来考虑问题,每次将前边求模之后的数保存下来,然后乘以10和这一位的数字进行相加的操作,一直重复这个步骤,知道最后一位,观察是否这个数字加之前剩余可以被整除,这就类似于我们小学做的除法的算式计算和一样

例如这样:![98b3372ecc07461e922c651a0051144d.png][]

例如求数字"98244353"是否可以被3整除

第一位:9%3=0,left=0;

第二位:8%3=2,left=2;

第三位:2\*10+2=22%3=1,left=1;

第四位:1\*10+4=14%3=2,left=2;

第五位:2\*10+4=24%3=0,left=0;

第六位3%3=0,left=0;

第七位4%3=1,left=1;

第八位:1\*10+3=13%3=1,left=1;

**所以不能被整除**

## 二.代码实现 ##

public boolean isDivide(String num, int k) {
            long left = 0;
            for (int i = 0; i < num.length(); ++i) {
                left = (left * 10 + num.charAt(i) - '0') % k;
            }
            return left == 0;
        }

## 三.找出字符串的可整除数组 ##

### 1.题目描述 ###

> 给你一个下标从 **0** 开始的字符串 `word` ，长度为 `n` ，由从 `0` 到 `9` 的数字组成。另给你一个正整数 `m` 。
> 
> `word` 的 **可整除数组** `div` 是一个长度为 `n` 的整数数组，并满足：
> 
>  *  如果 `word[0,...,i]` 所表示的 **数值** 能被 `m` 整除，`div[i] = 1`
>  *  否则，`div[i] = 0`
> 
> 返回`word` 的可整除数组。

力扣:[力扣][Link 1]

### 2.问题分析 ###

其实这个问题更好的解释上面的问题,如果这个位置的求余等于0,那么这里就是可以被整除的数字,一直往后叠加计算即可.

### 3.代码实现 ###

public int[] divisibilityArray(String word, int m) {
            int n = word.length();
            int[] div = new int[n];
            long left = 0;
            for (int i = 0; i < n; ++i) {
                int num = word.charAt(i) - '0';
                left = (left * 10 + num) % m;
                if (left == 0) {
                    div[i] = 1;
                }
    
            }
            return div;
        }

[98b3372ecc07461e922c651a0051144d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/04689991fd8f4063971488d281bc0536.png
[Link 1]: https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/description/