Q) Number of sub arrays in a given array and sum of sub array
elements.
For example given an array as shown below
Subarrays that can be formed are
[23], [23, 14], [23 , 14, 39], [23, 14, 39, 42]
[14], [14, 39], [14, 39, 42]
[39], [39, 42]
[42]
here 0th index element 23 occurs 4 times as first
element in subarray.
1st index element 14 occurs 6 times of which
3 times it occurs as first element in subarray and
remaining 3 times it occurs in combination with first element 23
2nd index
element 39 occurs 6 times of which
2 times it occurs as first element in subarray and
2 times it occurs in combination with first element 23
2 times it occurs in combination with second element 14
3rd index element 42 occurs 4 times of which
1 times it occurs as first element in subarray and
1 times it occurs in combination with first element 23
1 times it occurs in combination with second element 14
1 times it occurs in combination with third element 39
if n is the number of elements in an array, here n=4
23 occurs n-i times as first element where i =0 as 23 is 0th
index element
14 occurs n-i times as first element where i =1 as 14 is 1st
index element.
remaining n-i times it occurs in combination with first element.
39 occurs n- i times as first element where i=2
n-i times in combination with first element 23
n-I times in combination with second element 14….so i *(n-i) times
and so on..
so general formula is
number of times ith element occurs = (n – i)+ i*
(n-i)
Sum of sub array elements = number of times it occurs *
element
So the program is:
#include <stdio.h>
int main()
{
int n;
printf("enter
the number of elements\n");
scanf("%d",&n);
int
a[n],sum=0,i;
printf("\nEnter
array elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
sum
= sum+((n-i)+(n-i)*i)*a[i];
}
printf("sum
= %d",sum);
}
Q) find the maximum possible length of subarray In that subarray a[i+1]%a[i]==0 Every element in subarray is divisible by its previous element Your task is to find maximum length of subarray.
#include <stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int a[n],i,j,max1=0,res=0,max2;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i = 0 ; i < n ; i++)
if(max1 < a[i])
max1=a[i];
int cnt[max1+1] = {0};
int dp[max1+1] = {0};
for( i = 0 ; i < n ; i++)
cnt[ a[i] ]++ ;
for (i = max1 ; i > 0 ; i--)
{
max2=0;
for( j = 2*i ; j <= max1 ; j+=i )
if(max2<dp[j])
max2 = dp[j];
dp[i] = cnt[i] + max2;
}
for( i = 0 ; i < max1+1 ; i++)
if(res<dp[i])
res = dp[i];
printf("%d\n",res);
}
return 0;
}
