为了使一个数字可以被3整除而要删除的位数-yiteyi-C++库

给定一个非常大的数字num（1<=num<=10^1000），打印需要删除的位数，使该数字可以被3整除。如果不可能，则打印-1。

null

例如：

Input: num = "1234"Output: 1Explanation: we need to remove one digit that is 1 or 4, to make thenumber divisible by 3.on Input: num = "11"Output: -1Explanation: It is not possible to remove any digits and make it divisibleby 3.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法基于这样一个事实：一个数字是3的倍数，当且仅当其数字之和是3的倍数（参见这详细信息）。这里使用的一个重要观察结果是，如果答案存在，则答案最多为2。以下是该函数的唯一选项：

数字之和已经等于0模3。因此，我们不必擦除任何数字。
有这样一个数字等于模3的和。然后我们只需要删除一个数字
所有数字既不能被3整除，也不能等于模3之和。所以其中两个数字加起来就是数字，等于和模3，（2+2）模3=1，（1+1）模3=2

C++

                         // CPP program to find the minimum number of                       
                         // digits to be removed to make a large number                       
                         // divisible by 3.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to count the no of removal of digits                       
                         // to make a very large number divisible by 3                       
                         int                                     divisible(string num)                       
                         {                       
                                                 int                                     n = num.length();                       
           
                                                 // add up all the digits of num                       
                                                 int                                     sum = accumulate(begin(num),                       
                                                 end(num), 0) -                                     '0'                                     * 1;                       
           
                                                 // if num is already is divisible by 3                       
                                                 // then no digits are to be removed                       
                                                 if                                     (sum % 3 == 0)                       
                                                 return                                     0;                       
           
                                                 // if there is single digit, then it is                       
                                                 // not possible to remove one digit.                       
                                                 if                                     (n == 1)                       
                                                 return                                     -1;                       
           
                                                 // traverse through the number and find out                       
                                                 // if any number on removal makes the sum                       
                                                 // divisible by 3                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 if                                     (sum % 3 == (num[i] -                                     '0'                                     ) % 3)                       
                                                 return                                     1;                       
           
                                                 // if there are two numbers then it is                       
                                                 // not possible to remove two digits.                       
                                                 if                                     (n == 2)                       
                                                 return                                     -1;                       
           
                                                 // Otherwise we can always make a number                       
                                                 // multiple of 2 by removing 2 digits.                       
                                                 return                                     2;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 string num =                                     "1234"                                     ;                       
                                                 cout << divisible(num);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the                       
                         // minimum number of digits                       
                         // to be removed to make a                       
                         // large number divisible by 3.                       
                         import                                     java.io.*;                       
           
                         // function to count the no                       
                         // of removal of digits                       
                         // to make a very large                       
                         // number divisible by 3                       
                         class                                     GFG {                       
                                                 static                                     int                                     divisible(String num)                       
                                                 {                       
                                                 int                                     n = num.length();                       
           
                                                 // add up all the                       
                                                 // digits of num                       
                                                 int                                     sum =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 sum += (                                     int                                     )(num.charAt(i));                       
           
                                                 // if num is already is                       
                                                 // divisible by 3 then                       
                                                 // no digits are to be                       
                                                 // removed                       
                                                 if                                     (sum %                                     3                                     ==                                     0                                     )                       
                                                 return                                     0                                     ;                       
           
                                                 // if there is single digit,                       
                                                 // then it is not possible                       
                                                 // to remove one digit.                       
                                                 if                                     (n ==                                     1                                     )                       
                                                 return                                     -                                     1                                     ;                       
           
                                                 // traverse through the number                       
                                                 // and find out if any number                       
                                                 // on removal makes the sum                       
                                                 // divisible by 3                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 if                                     (sum %                                     3                                     == (num.charAt(i) -                                     '0'                                     ) %                                     3                                     )                       
                                                 return                                     1                                     ;                       
           
                                                 // if there are two numbers                       
                                                 // then it is not possible                       
                                                 // to remove two digits.                       
                                                 if                                     (n ==                                     2                                     )                       
                                                 return                                     -                                     1                                     ;                       
           
                                                 // Otherwise we can always                       
                                                 // make a number multiple                       
                                                 // of 2 by removing 2 digits.                       
                                                 return                                     2                                     ;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 String num =                                     "1234"                                     ;                       
                                                 System.out.println(divisible(num));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Raj                       

Python3

                         # Python3 program to find the                       
                         # minimum number of digits to                       
                         # be removed to make a large                       
                         # number divisible by 3.                       
           
                         # function to count the                       
                         # no of removal of digits                       
                         # to make a very large                       
                         # number divisible by 3                       
           
           
                         def                                     divisible(num):                       
                                                 n                                     =                                     len                                     (num)                       
           
                                                 # add up all the digits of num                       
                                                 sum_                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 sum_                                     +                                     =                                     int                                     (num[i])                       
           
                                                 # if num is already is                       
                                                 # divisible by 3 then no                       
                                                 # digits are to be removed                       
                                                 if                                     (sum_                                     %                                     3                                     =                                     =                                     0                                     ):                       
                                                 return                                     0                       
           
                                                 # if there is single digit,                       
                                                 # then it is not possible                       
                                                 # to remove one digit.                       
                                                 if                                     (n                                     =                                     =                                     1                                     ):                       
                                                 return                                     -                                     1                       
           
                                                 # traverse through the number                       
                                                 # and find out if any number                       
                                                 # on removal makes the sum                       
                                                 # divisible by 3                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     (sum_                                     %                                     3                                     =                                     =                                     int                                     (num[i])                                     %                                     3                                     ):                       
                                                 return                                     1                       
           
                                                 # if there are two numbers                       
                                                 # then it is not possible                       
                                                 # to remove two digits.                       
                                                 if                                     (n                                     =                                     =                                     2                                     ):                       
                                                 return                                     -                                     1                       
           
                                                 # Otherwise we can always                       
                                                 # make a number multiple of                       
                                                 # 2 by removing 2 digits.                       
                                                 return                                     2                       
           
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 num                                     =                                     "1234"                       
                                                 print                                     (divisible(num))                       
           
                         # This code is contributed by mits                       

C#

                         // C# program to find the                       
                         // minimum number of digits                       
                         // to be removed to make a                       
                         // large number divisible by 3.                       
                         using                                     System;                       
           
                         // function to count the no                       
                         // of removal of digits                       
                         // to make a very large                       
                         // number divisible by 3                       
                         class                                     GFG {                       
                                                 static                                     int                                     divisible(String num)                       
                                                 {                       
                                                 int                                     n = num.Length;                       
           
                                                 // add up all the                       
                                                 // digits of num                       
                                                 int                                     sum = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 sum += (                                     int                                     )(num[i]);                       
           
                                                 // if num is already is                       
                                                 // divisible by 3 then                       
                                                 // no digits are to be                       
                                                 // removed                       
                                                 if                                     (sum % 3 == 0)                       
                                                 return                                     0;                       
           
                                                 // if there is single digit,                       
                                                 // then it is not possible                       
                                                 // to remove one digit.                       
                                                 if                                     (n == 1)                       
                                                 return                                     -1;                       
           
                                                 // traverse through the number                       
                                                 // and find out if any number                       
                                                 // on removal makes the sum                       
                                                 // divisible by 3                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 if                                     (sum % 3 == (num[i] -                                     '0'                                     ) % 3)                       
                                                 return                                     1;                       
           
                                                 // if there are two numbers                       
                                                 // then it is not possible                       
                                                 // to remove two digits.                       
                                                 if                                     (n == 2)                       
                                                 return                                     -1;                       
           
                                                 // Otherwise we can always                       
                                                 // make a number multiple                       
                                                 // of 2 by removing 2 digits.                       
                                                 return                                     2;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 string                                     num =                                     "1234"                                     ;                       
                                                 Console.WriteLine(divisible(num));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to find the                       
                         // minimum number of digits to                       
                         // be removed to make a large                       
                         // number divisible by 3.                       
           
                         // function to count the                       
                         // no of removal of digits                       
                         // to make a very large                       
                         // number divisible by 3                       
           
                         function                                     divisible(                                     $num                                     )                       
                         {                       
                                                 $n                                     =                                     strlen                                     (                                     $num                                     );                       
           
                                                 // add up all the digits of num                       
                                                 $sum                                     = (                                     $num                                     ); (                                     $num                                     ); 0 -                                     '0'                                     ;                       
           
                                                 // if num is already is                       
                                                 // divisible by 3 then no                       
                                                 // digits are to be removed                       
                                                 if                                     (                                     $sum                                     % 3 == 0)                       
                                                 return                                     0;                       
           
                                                 // if there is single digit,                       
                                                 // then it is not possible                       
                                                 // to remove one digit.                       
                                                 if                                     (                                     $n                                     == 1)                       
                                                 return                                     -1;                       
           
                                                 // traverse through the number                       
                                                 // and find out if any number                       
                                                 // on removal makes the sum                       
                                                 // divisible by 3                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 if                                     (                                     $sum                                     % 3 == (                                     $num                                     [                                     $i                                     ] -                                     '0'                                     ) % 3)                       
                                                 return                                     1;                       
           
                                                 // if there are two numbers                       
                                                 // then it is not possible                       
                                                 // to remove two digits.                       
                                                 if                                     (                                     $n                                     == 2)                       
                                                 return                                     -1;                       
           
                                                 // Otherwise we can always                       
                                                 // make a number multiple of                       
                                                 // 2 by removing 2 digits.                       
                                                 return                                     2;                       
                         }                       
           
                         // Driver Code                       
                         $num                                     =                                     "1234"                                     ;                       
                         echo                                     divisible(                                     $num                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find the minimum number of                       
                         // digits to be removed to make a large number                       
                         // divisible by 3.                       
           
                         // function to count the no of removal of digits                       
                         // to make a very large number divisible by 3                       
                         function                                     divisible(num)                       
                         {                       
                                                 let n = num.length;                       
           
                                                 // add up all the digits of num                       
                                                 let sum = 0;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 sum += (num.charAt(i));                       
           
                                                 // if num is already is divisible by 3                       
                                                 // then no digits are to be removed                       
                                                 if                                     (sum % 3 == 0)                       
                                                 return                                     0;                       
           
                                                 // if there is single digit, then it is                       
                                                 // not possible to remove one digit.                       
                                                 if                                     (n == 1)                       
                                                 return                                     -1;                       
           
                                                 // traverse through the number and find out                       
                                                 // if any number on removal makes the sum                       
                                                 // divisible by 3                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 if                                     (sum % 3 == (num.charAt(i) -                                     '0'                                     ) % 3)                       
                                                 return                                     1;                       
           
                                                 // if there are two numbers then it is                       
                                                 // not possible to remove two digits.                       
                                                 if                                     (n == 2)                       
                                                 return                                     -1;                       
           
                                                 // Otherwise we can always make a number                       
                                                 // multiple of 2 by removing 2 digits.                       
                                                 return                                     2;                       
                         }                       
           
                         // Driver Code                       
           
                                                 let num =                                     "1234"                                     ;                       
                                                 document.write(divisible(num));                       
           
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出：

时间复杂性： O（n），其中n是数字的长度。

本文由 奋斗者 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章