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 si-1 = si+1 for i = 2, 3, …n-1. Specifically, we can set s1 = 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++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to solve the problemvoid 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 functionint main(){ int n = 9; // Call the solve function with n = 9 solve(9);} |
Java
// JAVA code for the above approach:public class GFG { // Function to solve the problem public static void solve(int n) { // If n is odd if (n % 2 == 1) { // 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 == 1) // If i is odd, print the negative number System.out.print(-num + " "); else // Otherwise, print the positive number System.out.print(num - 1 + " "); } // Print a newline character at the end System.out.println(); } // 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 == 1) System.out.print(-1 + " "); // Otherwise, print 1 else System.out.print(1 + " "); } // Print a newline character at the end System.out.println(); } } // Driver function public static void main(String[] args) { int n = 9; // Call the solve function with n = 9 solve(9); }}// this code is contributed by rambabuguphka |
Python3
def solve(n): # If n is odd if n % 2: # Calculate the number to be added and subtracted alternatively num = n // 2 # Iterate through the sequence and print the values for i in range(n): if i % 2: # If i is odd, print the negative number print(-num, end=" ") else: # Otherwise, print the positive number print(num - 1, end=" ") # Print a newline character at the end print() # If n is even else: # Iterate through the sequence and print the values for i in range(n): # If i is odd, print -1 if i % 2: print(-1, end=" ") # Otherwise, print 1 else: print(1, end=" ") # Print a newline character at the end print()# Driver functionif __name__ == "__main__": n = 9 # Call the solve function with n = 9 solve(9)# This code is contributed by shivamgupta310570 |
C#
using System;public class GFG{ // Function to solve the problem static void Solve(int n) { // If n is odd if (n % 2 != 0) { // 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 != 0) // If i is odd, print // the negative number Console.Write(-num + " "); // Otherwise, print the // positive number else Console.Write(num - 1 + " "); } // Print a newline character // at the end Console.WriteLine(); } // 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 != 0) Console.Write(-1 + " "); // Otherwise, print 1 else Console.Write(1 + " "); } // Print a newline character // at the end Console.WriteLine(); } } // Driver function public static void Main(string[] args) { int n = 9; // Call the solve function with n = 9 Solve(n); }}// This code is contributed by akshitaguprzj3 |
Javascript
// Function to solve the problemfunction solve(n) { // If n is odd if (n % 2) { // Calculate the number to be // added and subtracted // alternatively let num = Math.floor(n / 2); // Iterate through the sequence // and print the values for (let i = 0; i < n; i++) { if (i % 2) // If i is odd, print // the negative number console.log(-num + " "); // Otherwise, print the // positive number else console.log(num - 1 + " "); } // Print a newline character // at the end console.log(); } // If n is even else { // Iterate through the sequence // and print the values for (let i = 0; i < n; i++) { // If i is odd, print -1 if (i % 2) console.log(-1 + " "); // Otherwise, print 1 else console.log(1 + " "); } // Print a newline character // at the end console.log(); }}// Driver functionlet n = 9;solve(9); |
Output
3 -4 3 -4 3 -4 3 -4 3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
