Generate an Array such that Average of triplet exist in given Array
Given an array A[] of length N and your task is to find an array B[] of size N+2, such that Average of (B[i], B[i+1], B[i+2]) equals to A[i] for each i (1 <= i <= N) .
Note: First two elements B[] must be zero.
Examples:
Input: N = 1, A[] = {3}
Output: B[] = {0, 0, 9}
Explanation: Let us understand it for each value of i (1 <= i <= 1)
- For i = 1: Average of (B[1], B[1+1], B[1+2]) = (0+0+9)/3 = 3. A[1] = 3. A[1] is equal to Average of (B[1], B[1+1], B[1+2]). Thus, output array B[] is correct.
Input: N = 4, A[] = {1, 3, 6, 5}
Output: {0, 0, 3, 6, 9, 0}
Explanation: The explanation is as follows:
- For i = 1: Average of (B[1], B[1+1], B[1+2]) = (0+0+3)/3 = 1. A[1] = 1. A[1] is equal to average of (B[1], B[1+1], B[1+2]).
- For i = 2: Average of (B[2], B[2+1], B[2+2]) = (0+3+6)/3 = 3. A[2] = 3. A[2] is equal to average of (B[2], B[2+1], B[2+2]).
- For i = 3: Average of (B[3], B[3+1], B[3+2]) = (3+6+9)/3 = 6. A[3] = 6. A[3] is equal to Average of (B[3], B[3+1], B[3+2]).
- For i = 4: Average of (B[4], B[4+1], B[4+2]) = (6+9+0)/3 = 5. A[4] = 5. A[4] = Average of (B[4], B[4+1], B[4+2]).
The condition met for each value of i. Thus, B[] is correct.
Approach: Implement the idea below to solve the problem
This problem can be solved using some mathematics, First we have to create a vector let say B and initialize first two elements of B[] as 0. For each N follow the below mentioned steps:
- Get sum of B[i] and B[i+1]
- The sum of current three consecutives of B[] will be: A[i]*3
- Third element, ie. B[i+2] will be: A[i]*3 – Sum(B[i] and B[i+1])
- Insert obtained Third element into vector B.
Steps were taken to solve the problem:
- Create a vector let say B.
- Initialize first two elements of B as 0.
- Create a variable let say j and initialize it to 0.
- Run a loop from i = 0 to i < N and follow below mentioned steps under the scope of loop:
- SumOfFirstTwo = B[j] + B[j+1]
- TotalSum = 3*A[i]
- ThirdElement = TotalSum – SumOfFirstTwo
- Insert value of ThirdElement into B.
- Increment j.
- Print the array B.
Below is the code to implement the approach:
C++
// CPP code to implement the approach #include <iostream> #include <vector> using namespace std; // Function to calculate // the required sequence vector< int > find_Sequence( int N, vector< int >& A) { // Vector to store the elements vector< int > B = { 0, 0 }; // Implementation of discussed approach int j = 0; for ( int i = 0; i < N; i++) { int sumOfFirstTwo = B[j] + B[j + 1]; int TotalSum = A[i] * 3; int thirdElement = TotalSum - sumOfFirstTwo; B.push_back(thirdElement); j++; } // returning vector return B; } // Main Function int main() { // Input int N = 4; vector< int > A = { 1, 3, 6, 5 }; // Function call vector< int > originalSequence = find_Sequence(N, A); // Loop for Printing the required sequence for ( int i = 0; i < originalSequence.size(); i++) { cout << originalSequence[i] << " "; } return 0; } |
Java
import java.util.*; public class Program { // Function to calculate the required sequence static List<Integer> findSequence( int N, List<Integer> A) { // List to store the elements List<Integer> B = new ArrayList<>(); B.add( 0 ); B.add( 0 ); // Implementation of the discussed approach int j = 0 ; for ( int i = 0 ; i < N; i++) { int sumOfFirstTwo = B.get(j) + B.get(j + 1 ); int totalSum = A.get(i) * 3 ; int thirdElement = totalSum - sumOfFirstTwo; B.add(thirdElement); j++; } // Returning list return B; } // Main Function public static void main(String[] args) { // Input int N = 4 ; List<Integer> A = List.of( 1 , 3 , 6 , 5 ); // Function call List<Integer> originalSequence = findSequence(N, A); // Loop for Printing the required sequence for ( int element : originalSequence) { System.out.print(element + " " ); } System.out.println(); } } |
Python3
def find_sequence(N, A): # List to store the elements B = [ 0 , 0 ] j = 0 for i in range (N): sum_of_first_two = B[j] + B[j + 1 ] total_sum = A[i] * 3 third_element = total_sum - sum_of_first_two B.append(third_element) j + = 1 # Returning list return B # Main Function if __name__ = = "__main__" : # Input N = 4 A = [ 1 , 3 , 6 , 5 ] # Function call original_sequence = find_sequence(N, A) # Loop for printing the required sequence for i in range ( len (original_sequence)): print (original_sequence[i], end = " " ) |
C#
using System; using System.Collections.Generic; class Program { // Function to calculate the required sequence static List< int > FindSequence( int N, List< int > A) { // List to store the elements List< int > B = new List< int > { 0, 0 }; // Implementation of the discussed approach int j = 0; for ( int i = 0; i < N; i++) { int sumOfFirstTwo = B[j] + B[j + 1]; int totalSum = A[i] * 3; int thirdElement = totalSum - sumOfFirstTwo; B.Add(thirdElement); j++; } // Returning list return B; } // Main Function static void Main() { // Input int N = 4; List< int > A = new List< int > { 1, 3, 6, 5 }; // Function call List< int > originalSequence = FindSequence(N, A); // Loop for Printing the required sequence foreach ( int element in originalSequence) { Console.Write(element + " " ); } Console.WriteLine(); } } |
Javascript
function findSequence(N, A) { // Array to store the elements let B = [0, 0]; let j = 0; for (let i = 0; i < N; i++) { let sumOfFirstTwo = B[j] + B[j + 1]; let totalSum = A[i] * 3; let thirdElement = totalSum - sumOfFirstTwo; B.push(thirdElement); j++; } // Returning result array return B; } // Driver Code let N = 4; let A = [1, 3, 6, 5]; // Function call let originalSequence = findSequence(N, A); // Printing the resulting sequence console.log(originalSequence.join( " " )); |
0 0 3 6 9 0
Time Complexity: O(N)
Auxiliary Space: O(1)