原文:
给定一个数字 n，只去掉一个数字，使这个数字能被 6 整除(使它尽可能大)。打印必须移除的位置，如果不可能，则打印-1。
示例:
input: 123
output: 3
explanation: remove 3rd position element and
hence the number is 12, which is divisible
by 6 and is the greatest possible.
input: 134
output: -1
explanation: not possible to remove any and
make it divisible by 6.
input: 4510222
output: 1
explanation: remove either 4 or 1 to make it
divisible by 6\. the numbers after removing 4
and 1 are 510222 and 450222 respectively.
so, remove 1st position to make it the
greatest possible.
天真方法: 遍历每一个元素，检查减去它后的数是否能被 6 整除，然后存储最大可能数。当 n 是一个非常大的数字，其可除性无法由%运算符检查时，这将不起作用。它只会对较小的 n 起作用。
高效方法: 把输入当成一串，想一想可能的情况。你可以检查任何 整除的可能性，如果它能被 2 和 3 整除，那么它也能被 6 整除。将出现的两种情况是
1) 当单位的数字为奇数时 当最后一位数字为奇数时，唯一可能的方法就是去掉最后一位数字，使其能被 6 整除。所以去掉最后一个数字，检查总和% 3 == 0，确保去掉最后一个数字后，n 的第二个最后一个数字是偶数，它的总和% 3 == 0，那么你得到的答案是必须去掉的第 n 个位置。如果有任何一种情况失败了，那么你就不能去掉任何一个数字使它能被 6 整除。
2) 当单位的位数为偶数时 在这种情况下，有多个选择。设和是给定数的位数之和。我们可以删除任何数字 d(除了单位位数字，如果十的位数字是奇数，那么这个数字仍然是 2 的倍数)，其和% 3 == d % 3。这是因为删除那个数字后，总和是 3 的倍数。
现在，为了最大化这个数，我们需要在最大的地方找到满足上述条件的数字。 例: 1。number = 4510222 位数总和= 4 5 1 2 2 2 = 16 总和% 3 = 1 现在，我们可以删除位数 1 和 4(因为 1 % 3 = 3 和 4 % 3 = 1) 如果我们删除 1，我们将得到 number 450222。如果我们删除 4，我们得到数字 510222 我们删除最大的数字(最左边)，下一个数字大于被删除的数字。 2。number = 7510222 位数之和= 7 5 1 0 2 2 = 19 位数之和% 3 = 1 位数 7 和 1 可以根据上述pg电子试玩链接的解决方案删除，分别给出数字 510222 和 750222。这里，删除最大的(最左边的)索引给出较小的结果，因为 7 > 5。这在上述情况下起作用，因为 4 < 5。
正确答案: 找到最左边同时满足两个约束的数字 1。总和% 3 ==数字% 3 2。数字<紧接着的下一个数字 如果你不能最大化某物的加法，试着最小化它的减少。如果找不到数字，数字小于紧接的右数字，则遵循上述方法。如果您从右侧删除某些内容，该数字将是最大可能值，因为您删除的是最低位的数字。 完成后，如果找到任何这样的元素，打印索引，否则只需打印-1。
以下是上述方法的实施情况
c
// c program to print digit's position
// to be removed to make number
// divisible by 6
#include
using namespace std;
// function to print the number divisible
// by 6 after exactly removing a digit
void greatest(string s)
{
int n = s.length();
int a[n];
// stores the sum of all elements
int sum = 0;
// traverses the string and converts
// string to number array and sums up
for (int i = 0; i < n; i ) {
a[i] = s[i] - '0';
sum = a[i];
}
if (a[n - 1] % 2) // odd check
{
// if second last is odd or
// sum of n-1 elements are not
// divisible by 3.
if (a[n - 2] % 2 != 0 or (sum - a[n - 1]) % 3 != 0) {
cout << "-1" << endl;
}
// second last is even and
// print n-1 elements
// removing last digit
else {
// last digit removed
cout << n << endl;
}
}
else {
int re = sum % 3;
int del = -1;
// counter to check if any
// element after removing,
// its sum%3==0
int flag = 0;
// traverse till second last element
for (int i = 0; i < n - 1; i ) {
// to check if any element
// after removing,
// its sum%3==0
if ((a[i]) % 3 == re) {
// the leftmost element
if (a[i 1] > a[i]) {
del = i;
flag = 1;
// break at the leftmost
// element
break;
}
else {
// stores the right most
// element
del = i;
}
}
}
// if no element has been found
// as a[i 1]>a[i]
if (flag == 0) {
// if second last is even, then
// remove last if (sum-last)%3==0
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3)
del = n - 1;
}
// if no element which on removing
// gives sum%3==0
if (del == -1)
cout << -1 << endl;
else {
cout << del 1 << endl;
}
}
}
// driver program to test the above function
int main()
{
string s = "7510222";
greatest(s);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print digit's position
// to be removed to make number
// divisible by 6
import java.util.*;
class solution
{
// function to print the number divisible
// by 6 after exactly removing a digit
static void greatest(string s)
{
int n = s.length();
int[] a = new int[n];
// stores the sum of all elements
int sum = 0;
// traverses the string and converts
// string to number array and sums up
for (int i = 0; i < n; i )
{
a[i] = s.charat(i) - '0';
sum = a[i];
}
if (a[n - 1] % 2 !=0) // odd check
{
// if second last is odd or
// sum of n-1 elements are not
// divisible by 3.
if (a[n - 2] % 2 != 0 || (sum - a[n - 1]) % 3 != 0)
{
system.out.println("-1");
}
// second last is even and
// print n-1 elements
// removing last digit
else
{
// last digit removed
system.out.println(n);
}
}
else
{
int re = sum % 3;
int del = -1;
// counter to check if any
// element after removing,
// its sum%3==0
int flag = 0;
// traverse till second last element
for (int i = 0; i < n - 1; i )
{
// to check if any element
// after removing,
// its sum%3==0
if ((a[i]) % 3 == re)
{
// the leftmost element
if (a[i 1] > a[i])
{
del = i;
flag = 1;
// break at the leftmost
// element
break;
}
else
{
// stores the right most
// element
del = i;
}
}
}
// if no element has been found
// as a[i 1]>a[i]
if (flag == 0)
{
// if second last is even, then
// remove last if (sum-last)%3==0
if (a[n - 2] % 2 == 0 && re == a[n - 1] % 3)
del = n - 1;
}
// if no element which on removing
// gives sum%3==0
if (del == -1)
system.out.println(-1);
else
{
system.out.println(del 1);
}
}
}
// driver program to test the above function
public static void main(string args[])
{
string s = "7510222";
greatest(s);
}
}
//this code is contributed by
//surendra_gangwar
python 3
# python program to print digit's position
# to be removed to make number
# divisible by 6
import math as mt
# function to print the number divisible
# by 6 after exactly removing a digit
def greatest(s):
n = len(s)
a=[0 for i in range(n)]
# stores the sum of all elements
sum = 0
# traverses the string and converts
# string to number array and sums up
for i in range(n):
a[i] = ord(s[i]) - ord('0')
sum = a[i]
if (a[n - 1] % 2): # odd check
# if second last is odd or
# sum of n-1 elements are not
# divisible by 3.
if (a[n - 2] % 2 != 0 or (sum - a[n - 1]) % 3 != 0):
print("-1")
# second last is even and
# prn-1 elements
# removing last digit
else:
# last digit removed
print(n)
else:
re = sum % 3
dell = -1
# counter to check if any
# element after removing,
# its sum%3==0
flag = 0
# traverse till second last element
for i in range(n-1):
# to check if any element
# after removing,
# its sum%3==0
if ((a[i]) % 3 == re):
# the leftmost element
if (a[i 1] > a[i]):
dell = i
flag = 1
# break at the leftmost
# element
break
else:
# stores the right most
# element
dell = i
# if no element has been found
# as a[i 1]>a[i]
if (flag == 0):
# if second last is even, then
# remove last if (sum-last)%3==0
if (a[n - 2] % 2 == 0 and re == a[n - 1] % 3):
dell = n - 1
# if no element which on removing
# gives sum%3==0
if (dell == -1):
print("-1")
else:
print(dell 1)
# driver program to test the above function
s = "7510222"
greatest(s)
#this code is contributed by mohit kumar 29
c
// c# program to print digit's position
// to be removed to make number
// divisible by 6
using system;
class gfg
{
// function to print the number divisible
// by 6 after exactly removing a digit
static void greatest(string s)
{
int n = s.length;
int[] a = new int[n];
// stores the sum of all elements
int sum = 0;
// traverses the string and converts
// string to number array and sums up
for (int i = 0; i < n; i )
{
a[i] = s[i] - '0';
sum = a[i];
}
if (a[n - 1] % 2 != 0) // odd check
{
// if second last is odd or
// sum of n-1 elements are not
// divisible by 3.
if (a[n - 2] % 2 != 0 ||
(sum - a[n - 1]) % 3 != 0)
{
console.write("-1");
}
// second last is even and
// print n-1 elements
// removing last digit
else
{
// last digit removed
console.write(n);
}
}
else
{
int re = sum % 3;
int del = -1;
// counter to check if any
// element after removing,
// its sum%3==0
int flag = 0;
// traverse till second last element
for (int i = 0; i < n - 1; i )
{
// to check if any element
// after removing,
// its sum%3==0
if ((a[i]) % 3 == re)
{
// the leftmost element
if (a[i 1] > a[i])
{
del = i;
flag = 1;
// break at the leftmost
// element
break;
}
else
{
// stores the right most
// element
del = i;
}
}
}
// if no element has been found
// as a[i 1]>a[i]
if (flag == 0)
{
// if second last is even, then
// remove last if (sum-last)%3==0
if (a[n - 2] % 2 == 0 &&
re == a[n - 1] % 3)
del = n - 1;
}
// if no element which on removing
// gives sum%3==0
if (del == -1)
console.write(-1);
else
{
console.write(del 1);
}
}
}
// driver code
public static void main()
{
string s = "7510222";
greatest(s);
}
}
// this code is contributed
// by chitranayal
服务器端编程语言（professional hypertext preprocessor 的缩写）
$a[$i])
{
$del = $i;
$flag = 1;
// break at the leftmost
// element
break;
}
else
{
// stores the right most
// element
$del = $i;
}
}
}
// if no element has been found
// as a[i 1]>a[i]
if ($flag == 0)
{
// if second last is even, then
// remove last if (sum-last)%3==0
if ($a[$n - 2] % 2 == 0 and
$re == $a[$n - 1] % 3)
$del = $n - 1;
}
// if no element which on removing
// gives sum%3==0
if ($del == -1)
echo -1, "\n";
else
{
echo $del 1, "\n";
}
}
}
// driver code
$s = "7510222";
greatest($s);
// this code is contributed by ajit
?>
java 描述语言
输出:
3
时间复杂度: o(位数)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
