Generate sequence with equal sum of adjacent integers

Given an integer N, find a sequence of N integers such that the sum of all integers in the sequence is equal to the sum of any two adjacent integers in the sequence.

Examples:

Input: N = 4
Output: 1 -1 1 -1
Explanation: Total sum of the four integers is 0 and the sum of any two adjacent integers is also 0.

Input: N = 5
Output: 1 -2 1 -2 1
Explanation: Total sum of the four integers is -1 and the sum of any two adjacent integers is also -1.

Approach: To solve the problem follow the below idea:

• For even n, we can use the array [-1, 1, -1, 1, …, -1, 1] as a solution. This array has a length of n, and the sum of any two adjacent elements is 0, as well as the sum of the whole array.
• For odd n, we can construct an array s of length n using two fixed values a and b, such that s_i-1 = s_i+1  for i = 2, 3, …n-1. Specifically, we can set s₁ = a and s2 = b, and then create the array s = [a, b, a, b, …, a, b, a]. We can then solve for ‘a’ and ‘b’ using the fact that the sum of any two adjacent elements and the sum of the whole array must be equal.
• If we let k be a positive integer such that n = 2k+1, then we can find values for ‘a’ and ‘b’ that satisfy the conditions. Specifically, we can set a = k-1 and b = -k, which produces the array [k-1, -k, k-1, -k, …, k-1, -k, k-1]. This array has a length of n, and the sum of any two adjacent elements is k-1-k = -1, as well as the sum of the whole array being k(k-1)-(k-1)k = 0.
• However, there is no solution for n = 3, as a = 0 and b = 0 do not satisfy the conditions. In general, the array we constructed will not work if a or b is equal to 0. Therefore, we must have k ≥ 2 to ensure that both a and b are nonzero.
• Overall, this approach shows that if there is a solution for even n, then there is a solution for odd n greater than or equal to 5.

Follow the steps to solve the problem:

• Initialize an integer variable ‘num’ with the value N/2.
• If N is even print 1, -1, ………, 1, -1
• If N is odd :
  • iterate through the sequence of integers from 1 to N.
  • If i is odd, print -num, otherwise print num-1.

Below is the implementation for the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;

// Function to solve the problem
void solve(int n)
{

    // If n is odd
    if (n % 2) {

        // Calculate the number to be
        // added and subtracted
        // alternatively
        int num = n / 2;

        // Iterate through the sequence
        // and print the values
        for (int i = 0; i < n; i++) {
            if (i % 2)

                // If i is odd, print
                // the negative number
                cout << -num << " ";

            // Otherwise, print the
            // positive number
            else
                cout << num - 1 << " ";
        }

        // Print a newline character
        // at the end
        cout << endl;
    }

    // If n is even
    else {

        // Iterate through the sequence
        // and print the values
        for (int i = 0; i < n; i++) {

            // If i is odd, print -1
            if (i % 2)
                cout << -1 << " ";

            // Otherwise, print 1
            else
                cout << 1 << " ";
        }

        // Print a newline character
        // at the end
        cout << endl;
    }
}

// Driver function
int main()
{
    int n = 9;

    // Call the solve function with n = 9
    solve(9);
}

3 -4 3 -4 3 -4 3 -4 3 

Time Complexity: O(N)
Auxiliary Space: O(1)

Given an integer N, find a sequence of N integers such that the sum of all integers in the sequence is equal to the sum of any two adjacent integers in the sequence.

Examples:

Input: N = 4
Output: 1 -1 1 -1
Explanation: Total sum of the four integers is 0 and the sum of any two adjacent integers is also 0.

Input: N = 5
Output: 1 -2 1 -2 1
Explanation: Total sum of the four integers is -1 and the sum of any two adjacent integers is also -1.

Approach: To solve the problem follow the below idea:

• For even n, we can use the array [-1, 1, -1, 1, …, -1, 1] as a solution. This array has a length of n, and the sum of any two adjacent elements is 0, as well as the sum of the whole array.
• For odd n, we can construct an array s of length n using two fixed values a and b, such that s_i-1 = s_i+1  for i = 2, 3, …n-1. Specifically, we can set s₁ = a and s2 = b, and then create the array s = [a, b, a, b, …, a, b, a]. We can then solve for ‘a’ and ‘b’ using the fact that the sum of any two adjacent elements and the sum of the whole array must be equal.
• If we let k be a positive integer such that n = 2k+1, then we can find values for ‘a’ and ‘b’ that satisfy the conditions. Specifically, we can set a = k-1 and b = -k, which produces the array [k-1, -k, k-1, -k, …, k-1, -k, k-1]. This array has a length of n, and the sum of any two adjacent elements is k-1-k = -1, as well as the sum of the whole array being k(k-1)-(k-1)k = 0.
• However, there is no solution for n = 3, as a = 0 and b = 0 do not satisfy the conditions. In general, the array we constructed will not work if a or b is equal to 0. Therefore, we must have k ≥ 2 to ensure that both a and b are nonzero.
• Overall, this approach shows that if there is a solution for even n, then there is a solution for odd n greater than or equal to 5.

Follow the steps to solve the problem:

• Initialize an integer variable ‘num’ with the value N/2.
• If N is even print 1, -1, ………, 1, -1
• If N is odd :
  • iterate through the sequence of integers from 1 to N.
  • If i is odd, print -num, otherwise print num-1.

Below is the implementation for the above approach:

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;

// Function to solve the problem
void solve(int n)
{

    // If n is odd
    if (n % 2) {

        // Calculate the number to be
        // added and subtracted
        // alternatively
        int num = n / 2;

        // Iterate through the sequence
        // and print the values
        for (int i = 0; i < n; i++) {
            if (i % 2)

                // If i is odd, print
                // the negative number
                cout << -num << " ";

            // Otherwise, print the
            // positive number
            else
                cout << num - 1 << " ";
        }

        // Print a newline character
        // at the end
        cout << endl;
    }

    // If n is even
    else {

        // Iterate through the sequence
        // and print the values
        for (int i = 0; i < n; i++) {

            // If i is odd, print -1
            if (i % 2)
                cout << -1 << " ";

            // Otherwise, print 1
            else
                cout << 1 << " ";
        }

        // Print a newline character
        // at the end
        cout << endl;
    }
}

// Driver function
int main()
{
    int n = 9;

    // Call the solve function with n = 9
    solve(9);
}

3 -4 3 -4 3 -4 3 -4 3 

Time Complexity: O(N)
Auxiliary Space: O(1)