一个阵列的所有子阵列的乘积|集合 2
给定一个大小为 N 的整数数组arr【】,任务是找到数组的所有子数组的乘积。 举例:
输入: arr[] = {2,4} 输出: 64 解释: 这里,子阵是{2}、{2,4}和{4}。 每个子阵的产品是 2、8、4。 所有子阵列的乘积= 64 输入: arr[] = {1,2,3} 输出: 432 说明: 这里,子阵列为{1}、{1,2}、{1,2,3}、{2}、{2,3}、{3}。 每个子阵的产品是 1、2、6、2、6、3。 所有子阵列的乘积= 432
天真迭代的方法:这些方法请参考本帖。 方法:想法是统计所有子阵列中出现的每个元素的数量。为了计数,我们有以下观察:
- 在以 arr[i] 开始的每个子阵列中,都有以元素 arr[i] 开始的(N–I)这样的子集。 例如:
对于数组 arr[] = {1,2,3} N = 3,对于元素 2,即索引= 1 有(N–索引)= 3–1 = 2 的子集 {2}和{2,3}
- 对于任何元素 arr[i] ,都有(N–I)* I子阵列,其中 arr[i] 不是第一个元素。
对于数组 arr[] = {1,2,3} N = 3,对于元素 2,即索引= 1 有(N–索引)索引=(3–1) 1 = 2 个子集,其中 2 不是第一个元素。 {1,2}和{1,2,3}
因此,根据以上观察,每个元素的总数arr【I】出现在所有子阵列中,每个索引 I 由下式给出:
total_elements = (N - i) + (N - i)*i
total_elements = (N - i)*(i + 1)
其思想是将每个元素(N–I)*(I+1)的次数相乘,得到所有子阵列中元素的乘积。 以下是上述办法的实施情况:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the product of
// elements of all subarray
long int SubArrayProdct(int arr[],
int n)
{
// Initialize the result
long int result = 1;
// Computing the product of
// subarray using formula
for (int i = 0; i < n; i++)
result *= pow(arr[i],
(i + 1) * (n - i));
// Return the product of all
// elements of each subarray
return result;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << SubArrayProdct(arr, N)
<< endl;
return 0;
}
Java 语言(一种计算机语言,尤用于创建网站)
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the product of
// elements of all subarray
static int SubArrayProdct(int arr[], int n)
{
// Initialize the result
int result = 1;
// Computing the product of
// subarray using formula
for(int i = 0; i < n; i++)
result *= Math.pow(arr[i], (i + 1) *
(n - i));
// Return the product of all
// elements of each subarray
return result;
}
// Driver code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = new int[]{2, 4};
int N = arr.length;
// Function Call
System.out.println(SubArrayProdct(arr, N));
}
}
// This code is contributed by Pratima Pandey
Python 3
# Python3 program for the above approach
# Function to find the product of
# elements of all subarray
def SubArrayProdct(arr, n):
# Initialize the result
result = 1;
# Computing the product of
# subarray using formula
for i in range(0, n):
result *= pow(arr[i],
(i + 1) * (n - i));
# Return the product of all
# elements of each subarray
return result;
# Driver Code
# Given array arr[]
arr = [ 2, 4 ];
N = len(arr);
# Function Call
print(SubArrayProdct(arr, N))
# This code is contributed by Code_Mech
C
// C# program for the above approach
using System;
class GFG{
// Function to find the product of
// elements of all subarray
static int SubArrayProdct(int []arr, int n)
{
// Initialize the result
int result = 1;
// Computing the product of
// subarray using formula
for(int i = 0; i < n; i++)
result *= (int)(Math.Pow(arr[i], (i + 1) *
(n - i)));
// Return the product of all
// elements of each subarray
return result;
}
// Driver code
public static void Main()
{
// Given array arr[]
int []arr = new int[]{2, 4};
int N = arr.Length;
// Function Call
Console.Write(SubArrayProdct(arr, N));
}
}
// This code is contributed by Code_Mech
java 描述语言
<script>
// JavaScript program to implement
// the above approach
// Function to find the product of
// elements of all subarray
function SubArrayProdct(arr, n)
{
// Initialize the result
let result = 1;
// Computing the product of
// subarray using formula
for(let i = 0; i < n; i++)
result *= Math.pow(arr[i], (i + 1) *
(n - i));
// Return the product of all
// elements of each subarray
return result;
}
// Driver code
// Given array arr[]
let arr = [2, 4];
let N = arr.length;
// Function Call
document.write(SubArrayProdct(arr, N));
// This code is contributed by sanjoy_62.
</script>
Output:
64
时间复杂度: O(N) ,其中 N 为元素个数。 T5【辅助空间: O(1)
版权属于:月萌API www.moonapi.com,转载请注明出处