PROBLEM LINK: Div-3 Contest
Author: Bhagya , Rishika
Tester: Rishika
Editorialist: Bhagya
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Circular Addition
QUICK EXPLANATION:
The first line of each test file contains a integer N.
The next line contains N space separated integers which represent the elements of the cyclic array.
The third line contains a integer Q representing the number of operations that will be applied to the array.
Finally, Q lines follow, each one containing an integer X .
EXPLANATION:
Krish is a very smart kid who recently started learning computer programming. His mentor gave him a cyclic array A having N numbers, and he has to perform Q operations on this array. In each operation the coach would provide him with a number X. After each operation, every element of the cyclic array would be replaced by the sum of itself and the element lying X positions behind it in the cyclic array. All these replacements take place simultaneously. For example, if the cyclic array was [a, b, c, d], then after the operation with X = 1, the new array would be [a+d, b+a, c+b, d+c]. He needs to output the sum of the elements of the final array modulus 10^9+7. He made a program for it but it’s not very efficient. You know he is a beginner, so he wants you to make an efficient program for this task because he doesn’t want to disappoint his coach.
Constraints
1 <= N <= 100000
1 <= Ai<= 10^9
0 <= Q <= 1000000
0 <= X < N
SOLUTIONS:
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a[] = new int[n];
for(int i=0; i<n; i++)
a[i] = sc.nextInt();
int temp[] = new int[n];
for(int i=0; i<n; i++)
temp[i] = a[i];
int q = sc.nextInt();
while(q-- > 0)
{
int x = sc.nextInt();
x = x % a.length;
for(int i=0; i<n; i++)
{
int r = i - x;
if(r < 0)
r = n + r;
a[i] += temp[r];
}
for(int i=0; i<n; i++)
temp[i] = a[i];
}
int sum = 0;
for(int i=0; i<n; i++)
sum += a[i];
System.out.println(sum % ((int)Math.pow(10, 9) + 7));
}
}
