Given two arrays A and B of same size m. You have to find the sum of nth terms of Fibonacci like series (value of every term is sum of previous two terms) formed by every element of A as first and every element of B as second.
Examples:
Input : {1, 2, 3}, {4, 5, 6}, n = 3
Output : 63
Explanation :
A[] = {1, 2, 3};
B[] = {4, 5, 6};
n = 3;
All the possible series upto 3rd terms are:
We have considered every possible pair of A
and B and generated third term using sum of
previous two terms.
1, 4, 5
1, 5, 6
1, 6, 7
2, 4, 6
2, 5, 7
2, 6, 8
3, 4, 7
3, 5, 8
3, 6, 9
sum = 5+6+7+6+7+8+7+8+9 = 63
Input : {5, 8, 10}, {6, 89, 5}
Output : 369
The naive approach is to take every pair of the array A and B and make a Fibonacci series with them.
An efficient approach is based on below idea.
Store the original Fibonacci series in an array and multiply the first term by original_fib[n-2] and second term by original_fib[n-1].
Every element of array A, as well as B, will come m times so multiply them by m.
(m * (B[i] * original_fib[n-1]) ) + (m * (A[i] * original_fib[n-2]) )
By using the efficient method it can be written as
original_fib[]={0, 1, 1, 2, 3, 5, 8};
A[] = {1, 2, 3};
B[] = {4, 5, 6};
n = 3;
for (i to m)
sum = sum + 3*(B[i]*original_fib[2]) + 3*(A[i]*original_fib[1])
Below is the implementation of above approach:
C++
// CPP program to find sum of n-th terms// of a Fibonacci like series formed using// first two terms of two arrays.#include <bits/stdc++.h>using namespace std;int sumNth(int A[], int B[], int m, int n){ int res = 0; // if sum of first term is required if (n == 1) { for (int i = 0; i < m; i++) res = res + A[i]; } // if sum of second term is required else if (n == 2) { for (int i = 0; i < m; i++) res = res + B[i] * m; } else { // fibonacci series used to find the // nth term of every series int f[n]; f[0] = 0, f[1] = 1; for (int i = 2; i < n; i++) f[i] = f[i - 1] + f[i - 2]; for (int i = 0; i < m; i++) { // as every b[i] term appears m times and // every a[i] term also appears m times res = res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2])); } } return res;}int main(){ // m is the size of the array int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int n = 3; int m = sizeof(A)/sizeof(A[0]); cout << sumNth(A, B, m, n); return 0;} |
Java
// Java program to find sum of n-th terms// of a Fibonacci like series formed using// first two terms of two arrays.public class GFG { static int sumNth(int A[], int B[], int m, int n) { int res = 0; // if sum of first term is required if (n == 1) { for (int i = 0; i < m; i++) res = res + A[i]; } // if sum of second term is required else if (n == 2) { for (int i = 0; i < m; i++) res = res + B[i] * m; } else { // fibonacci series used to find the // nth term of every series int f[] = new int[n]; f[0] = 0; f[1] = 1; for (int i = 2; i < n; i++) f[i] = f[i - 1] + f[i - 2]; for (int i = 0; i < m; i++) { // as every b[i] term appears m times and // every a[i] term also appears m times res = res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2])); } } return res; } public static void main(String args[]) { // m is the size of the array int A[] = { 1, 2, 3 }; int B[] = { 4, 5, 6 }; int n = 3; int m = A.length; System.out.println(sumNth(A, B, m, n)); } // This code is contributed by ANKITRAI1} |
Python3
# Python3 program to find sum of # n-th terms of a Fibonacci like # series formed using first two # terms of two arrays.def sumNth(A, B, m, n): res = 0; # if sum of first term is required if (n == 1): for i in range(m): res = res + A[i]; # if sum of second term is required elif (n == 2): for i in range(m): res = res + B[i] * m; else: # fibonacci series used to find # the nth term of every series f = [0] * n; f[0] = 0; f[1] = 1; for i in range(2, n): f[i] = f[i - 1] + f[i - 2]; for i in range(m): # as every b[i] term appears m # times and every a[i] term also # appears m times res = (res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2]))); return res;# Driver code # m is the size of the arrayA = [1, 2, 3 ];B = [4, 5, 6 ];n = 3;m = len(A);print(sumNth(A, B, m, n));# This code is contributed by mits |
C#
// C# program to find sum of// n-th terms of a Fibonacci // like series formed using // first two terms of two arrays.using System;class GFG{ static int sumNth(int[] A, int[] B, int m, int n){ int res = 0; // if sum of first term is required if (n == 1) { for (int i = 0; i < m; i++) res = res + A[i]; } // if sum of second term is required else if (n == 2) { for (int i = 0; i < m; i++) res = res + B[i] * m; } else { // fibonacci series used to find // the nth term of every series int[] f = new int[n]; f[0] = 0; f[1] = 1; for (int i = 2; i < n; i++) f[i] = f[i - 1] + f[i - 2]; for (int i = 0; i < m; i++) { // as every b[i] term appears m // times and every a[i] term also // appears m times res = res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2])); } } return res;}// Driver Codepublic static void Main(String[] args){ // m is the size of the array int[] A = { 1, 2, 3 }; int[] B = { 4, 5, 6 }; int n = 3; int m = A.Length; Console.WriteLine(sumNth(A, B, m, n));}}// This code is contributed // by Kirti_Mangal |
PHP
<?php// PHP program to find sum of n-th terms// of a Fibonacci like series formed using// first two terms of two arrays.function sumNth(&$A, &$B, &$m, &$n){ $res = 0; // if sum of first term is required if ($n == 1) { for ($i = 0; $i < $m; $i++) $res = $res + $A[$i]; } // if sum of second term is required else if ($n == 2) { for ($i = 0; $i < $m; $i++) $res = $res + $B[$i] * $m; } else { // fibonacci series used to find // the nth term of every series $f = array(); $f[0] = 0; $f[1] = 1; for ($i = 2; $i < $n; $i++) $f[$i] = $f[$i - 1] + $f[$i - 2]; for ($i = 0; $i < $m; $i++) { // as every b[i] term appears m times // and every a[i] term also appears m times $res = $res + ($m * ($B[$i] * $f[$n - 1])) + ($m * ($A[$i] * $f[$n - 2])); } } return $res;}// Driver code // m is the size of the array$A = array(1, 2, 3 );$B = array(4, 5, 6 );$n = 3;$m = sizeof($A);echo (sumNth($A, $B, $m, $n));// This code is contributed // by Shivi_Aggarwal?> |
Javascript
<script>// javascript program to find sum of n-th terms// of a Fibonacci like series formed using// first two terms of two arrays. function sumNth(A , B , m , n) { var res = 0; // if sum of first term is required if (n == 1) { for (let i = 0; i < m; i++) res = res + A[i]; } // if sum of second term is required else if (n == 2) { for (let i = 0; i < m; i++) res = res + B[i] * m; } else { // fibonacci series used to find the // nth term of every series var f = Array(n).fill(0); f[0] = 0; f[1] = 1; for (let i = 2; i < n; i++) f[i] = f[i - 1] + f[i - 2]; for (i = 0; i < m; i++) { // as every b[i] term appears m times and // every a[i] term also appears m times res = res + (m * (B[i] * f[n - 1])) + (m * (A[i] * f[n - 2])); } } return res; } // m is the size of the array var A = [ 1, 2, 3 ]; var B = [ 4, 5, 6 ]; var n = 3; var m = A.length; document.write(sumNth(A, B, m, n));// This code is contributed by aashish1995 </script> |
Output:
63
Time Complexity: O(M + N), where M and N represents the size of the given two arrays.
Auxiliary Space: O(N), where N represents the size of the given array.
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
