数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学通过递减相邻对来创建零数组
问题陈述包括通过递减相邻对来创建一个零数组。
输入将给出数组，我们可以在数组上执行操作，即**从第 i 个和第 (i+1) 个索引减去 1，其中 0<=i<(数组大小−1)**。我们可以根据需要执行给定的操作，以使数组的元素变为零。数组将只包含正整数。
在这个问题中，我们将得到一个输入数组，我们需要检查是否可以通过执行任意次数上述操作将数组的所有元素转换为零。如果可以通过执行任意次数的操作将数组的所有元素转换为零，则需要打印“Yes”，否则需要打印“No”。
让我们通过以下示例来了解这个问题。
输入
a[]={1,2,5,4}
输出
Yes
**解释** − 对数组应用操作后，它变为
{1,2,5,4}={0,1,5,4}={0,0,4,4}
对 a[2] 和 a[3] 应用 4 次操作，我们得到 {0,0,0,0}。
由于可以通过多次应用指定的操作将数组转换为零数组，因此输出为 yes。
输入
a[]={3, 2, 2, 6}
输出
No
**解释** − 对数组应用操作后，
{3,2,2,6}={2,1,2,6}={1,0,2,6}={1,0,1,5}={1,0,0,4}
由于我们只能从 a[i] 和 a[i+1] 减去 1，并且无法将数组转换为零数组，因此无法进一步执行操作。因此，输出为 No。
有各种方法可以解决这个问题，以检查是否可以通过多次应用指定的操作将数组转换为零数组。让我们看看并理解解决这个问题的有效方法。
方法一
如果数组中奇数位置元素的和等于数组中偶数位置元素的和，则该数组可以转换为零数组。由于我们只能从 i 和 (i+1) 位置减去 1，因此要通过从奇数位置和偶数位置减去 1 来使数组成为零数组，只有当奇数位置元素的和等于偶数位置元素的和时才有可能。
例如，**{1,2,5,4}** 可以转换为零数组。
奇数位置元素的和，即 a[1]+a[3]=2+4=6
偶数位置元素的和，即 a[0]+a[2]=1+5=6
因此，它可以转换为零数组。
我们在方法中使用此逻辑来检查是否可以通过递减相邻对将数组转换为零数组。
在 C++ 中实现该方法的步骤
我们将创建一个函数来检查数组是否可以通过计算偶数位置和奇数位置的和来转换为零数组。
初始化两个变量来存储偶数位置和奇数位置的数字之和。
从 i=0 到 i<数组大小迭代 for 循环。
在 for 循环中迭代时，我们将检查 i 是否为偶数，如果为偶数，我们将把第 i 个位置对应的元素添加到我们将用来存储偶数位置数字之和的变量中，否则，如果 i 不是偶数，我们将把第 i 个位置对应的数字添加到另一个变量中，以存储奇数位置的和。
在整个数组迭代之后，我们将通过比较变量中存储的值来检查偶数位置的和是否等于奇数位置的和。
如果两者相等则返回 true，否则返回 false。
如果函数返回 true，则在输出中打印“Yes”，否则打印“No”。
示例
//C++ code to check if the array can be converted to zero array by decrementing adjacent pairs by 1
#include<bits/stdc++.h>
using namespace std;
//function to check if the array can be converted to a zero array
bool check(int a[],int N){
int even_sum=0; //to store sum of elements at even position
int odd_sum=0; //to store sum of elements at odd positions
//to find the sum of even and odd positions
for(int i=0;i<N;i++){
//if i is even
if(i%2==0){
even_sum += a[i];
}
else{
odd_sum += a[i];
}
}
if(even_sum==odd_sum){ //return true if sum of even positions is equal to odd positions
return true;
} else{
return false;
}
}
int main()
{
int a[]={2,8,3,12,5,9,17,8,8,11};
int N; //to store size of the array
N=sizeof(a)/sizeof(a[0]);
//calling the function
if(check(a,N)==true){
cout<<"Yes"<<endl;
} else{
cout<<"No"<<endl;
}
return 0;
}
输出
No
**时间复杂度** − O(N)，因为我们迭代数组以存储偶数位置和奇数位置的数字之和。
**空间复杂度** − O(1)，因为该方法没有占用额外的空间。
方法二
在这种方法中，我们将检查由给定数组形成的数字。如果由数组形成的数字是 11 的倍数，则可以通过多次从 a[i] 和 a[i+1] 减去 1 将数组转换为零数组。如果由给定数组形成的数字不是 11 的倍数，则该数组无法转换为零数组。
例如，数组为 **{3,2,2,6}**。
由数组形成的数字将是 3226。由于这个数字不是 11 的倍数，因此该数组无法转换为零数组。
如果给定数组为 **{1,2,5,4}**。
由数组形成的数字将是 1254。这个数字是 11 的倍数，因为 11*114 等于 1254。因此，可以通过执行操作将数组转换为零数组。
在 C++ 中实现该方法的步骤
我们将创建一个函数来检查由给定数组形成的数字是否是 11 的倍数。
初始化一个变量来存储由数组形成的数字。
我们将从 i=0 到 i<数组大小迭代 for 循环，并通过将其乘以 10 并添加第 i 个数字来不断更新数字。
一旦我们得到由数组形成的数字，我们将检查它是否能被 11 整除。如果它能被 11 整除，我们将打印 Yes，因为形成的数字是 11 的倍数，否则我们将打印 No。
**注意：**此方法仅适用于大小小于或等于 18 的数组，因为由数组形成的数字可能会超过数据类型的范围。
示例
// C++ code to check if the array can be converted to a zero array
// by decrementing the pairs of adjacent
#include <bits/stdc++.h>
using namespace std;
//function to check if the given array can be converted to a zero array
bool check(int a[], int N)
{
// to store the number formed by the given array
long long number = 0;
for (int i = 0; i < N; i++){
//update the number
number = number * 10 + a[i];
}
//if number is multiple of 11, it will be divisible by 11
if(number%11==0){
return true;
} else{
return false;
}
}
int main()
{
int a[] = {2,5,1,3,6,1 };
int N = sizeof(a) / sizeof(a[0]); //calculating size of the array
//calling the function
if (check(a, N)){
cout << "Yes"<<endl;
} else{
cout << "No"<<endl;
}
}
输出
Yes
**时间复杂度** − O(N)，因为我们迭代给定数组以获得由数组形成的数字
**空间复杂度** − O(1)，因为该方法没有占用额外的空间。
结论
本文讨论了检查给定数组是否可以通过递减相邻对将给定数组转换为零数组的问题。我们尝试使用简单的逻辑在 O(N) 运行时间和恒定空间内使用两种不同的方法在 C++ 中解决这个问题。
我希望在阅读本文后，您能理解这个问题以及解决这个问题的方法。
77 次浏览
