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 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 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); } |
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 function if __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 problem function 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 function let n = 9; solve(9); |
Output
3 -4 3 -4 3 -4 3 -4 3
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us