C++ 通过递减相邻的一对元素制作零数组

问题陈述包括通过递减相邻元素的一对元素制作零数组。

输入会给出数组，我们可以对数组执行操作，即 从第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}。

由于数组可以通过多次应用指定的操作转换为零数组，输出为是。

输入

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。

有多种方法可以解决该问题，检查数组是否通过任意次数的指定操作可以转换为零数组。让我们看看并理解解决问题的有效方法。

方法一

如果数组中奇数位置的元素之和等于偶数位置的元素之和，则数组可以转换为零数组。由于我们只能从奇数位置和偶数位置减去1，因此，通过从奇数位置和偶数位置减去1使数组成为零数组，只有在奇数位置上的元素之和等于偶数位置上的元素之和时，这才可能发生。

例如， {1,2,5,4} 可以转换为零数组。

奇数位置上的元素之和，即a[1]+a[3]=2+4=6

偶数位置上的元素之和，即a[0]+a[2]=1+5=6

因此，它可以转换为零数组。

我们使用此逻辑来检查是否通过减小邻接对可以将数组转换为零数组。

在C++中实现该方法的步骤：

创建一个函数，通过计算奇数位置和偶数位置的数字之和来检查数组是否可以转换为零数组。
初始化两个变量，用于存储偶数位置和奇数位置的数字之和。
在for循环中迭代，i从0到i<数组长度。
在for循环中迭代时，如果i是偶数，将第i个位置上的元素添加到变量中，该变量用于存储偶数位置的数字之和；否则，将第i个位置上的元素添加到另一个变量中，该变量用于存储奇数位置的数字之和。
在遍历整个数组后，通过比较存储在变量中的值，检查偶数位置的数字之和是否等于奇数位置的数字之和。
如果它们相等，则返回true；否则，返回false。
如果该函数返回true，则在输出中打印“Yes”，否则打印“N0”。

示例

//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)，因为该方法没有使用额外的空间。

方法2

在这个方法中，我们将检查由给定数组组成的数字。如果数组的数字形成的数是11的倍数，则可以通过无限次数地从a[i]和a[i+1]中减去1来将数组转换为零数组。如果由给定数组组成的数字不是11的倍数，则无法将数组转换为零数组。

例如，数组是 {3,2,2,6} 。

由数组组成的数为3226。由于3226不是11的倍数，无法将数组转换为零数组。

如果给定的数组是 {1,2,5,4} 。

由数组组成的数为1254。1254是11的倍数，因为11*114等于1254。因此，可以通过执行操作将数组转换为零数组。

在C++中实现该方法的步骤：

我们将创建一个函数来检查由给定数组组成的数字是否是11的倍数。
初始化一个变量来存储由数组组成的数字。
我们将在一个for循环中从i=0到i小于数组的大小进行迭代，并通过将其乘以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;
    }
}