Horje
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(" "));

Output

0 0 3 6 9 0

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


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
FIFO Principle of Queue FIFO Principle of Queue
Min Length String with All Substrings of Size N Min Length String with All Substrings of Size N
Maximum Ways to Cross the field Maximum Ways to Cross the field
Find Column with Maximum Zeros in Matrix Find Column with Maximum Zeros in Matrix
Minimum Cost with Bonus Items in Shopping Minimum Cost with Bonus Items in Shopping

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 17



 

Horje