## This question is taken from Hackerearth.com Akash is interested in a new function F such that, F(x) = GCD(1, x) + GCD(2, x) + ... + GCD(x, x) where GCD is the Greatest Common Divisor. Now, the problem is quite simple. Given an array A of size N, there are 2 types of queries: 1. C X Y : Compute the value of F( A[X] ) + F( A[X + 1] ) + F( A[X + 2] ) + .... + F( A[Y] ) (mod 10^9 + 7) 2. U X Y: Update the element of array A[X] = Y Input: First line of input contain integer N, size of the array. Next line contain N space separated integers the elements of A. Next line contain integer Q, number of queries. Next Q lines contain one of the two queries. Output: For each of the first type of query, output the required sum (mod 10^9 + 7). Constraints: 1 <= N <= 106 1 <= Q <= 105 1 <= Ai <= 5*105 For Update , 1 <= X <= N 1 <= Y <= 5*105 For Compute , 1 <= X <= Y <= N SAMPLE INPUT 3 3 4 3 6 C 1 2 C 1 3 C 3 3 U 1 4 C 1 3 C 1 2  SAMPLE OUTPUT 13 18 5 21 16  Explanation A[1] = 3, A[2] = 4, A[3] = 3 F(3) = GCD(1, 3) + GCD(2, 3) + GCD(3, 3) = 1 + 1 + 3 = 5. F(4) = GCD(1, 4) + GCD(2, 4) + GCD(3, 4) + GCD(4, 4) = 1 + 2 + 1 + 4 = 8. First query, the sum will be F(3) + F(4) = 5 + 8 = 13 (mod 10^9 + 7). Second query, the sum will be F(3) + F(4) + F(3) = 5 + 8 + 5 = 18 (mod 10^9 + 7). Third query, the sum will be F(3) = 5 (mod 10^9 + 7). Fourth query will update A[1] = 4. Fifth query, the sum will be F(4) + F(4) + F(3) = 8 + 8 + 5 = 21 (mod 10^9 + 7). Sixth query, the sum will be F(4) + F(4) = 8 + 8 = 16 (mod 10^9 + 7). Time Limit:1.0 sec(s) for each input file. Memory Limit:256 MB Source Limit:1024 KB Marking Scheme:Marks are awarded if any testcase passes. Allowed Languages:C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

Solution:

#include <stdio.h>

int gcd (int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}

int compute(int *a, int x, int y)
{
int sum = 0;

for(int i = x; i <= y; i++)
{
sum += a[i-1];
}
printf("%d\n", sum);
return 0;
}

int update(int *a, int x, int y)
{
int sum =0;
for(int j = 1; j < y; j++)
{
sum += gcd(j, y);
}
sum += y;

a[x - 1] = sum;

return 0;
}

int main()
{
int n;
int a[100000];
int nq;
int q[100000];
int i;
int x , y;
char c;
scanf("%d", &n);
for(i = 0; i < n; i++)
{
int t;
scanf("%d", &t);
int j;
for(j = 1; j < t; j++)
{
a[i] += gcd(j, t);
}
a[i] += t;
}
scanf("%d\n", &nq);

for(i = 0; i < nq; i++)
{
scanf("%c %d %d\n", &c, &x, &y);

if(c == 'C')
{
compute(&a, x, y);
}
else if (c == 'U')
{
update(&a, x, y);
}
else
printf("input = %c\n", c);
}
return 0;
}

## Saturday, 7 January 2017

### [Solved] Circular Array Rotation solution HackerRank

John Watson performs an operation called a right circular rotation on an array of integers, . After performing one right circular rotation operation, the array is transformed from  to .
Watson performs this operation  times. To test Sherlock's ability to identify the current element at a particular position in the rotated array, Watson asks  queries, where each query consists of a single integer, , for which you must print the element at index  in the rotated array (i.e., the value of ).
Input Format
The first line contains  space-separated integers, , and , respectively.
The second line contains  space-separated integers, where each integer  describes array element  (where ).
Each of the  subsequent lines contains a single integer denoting .
Constraints
Output Format
For each query, print the value of the element at index  of the rotated array on a new line.
Sample Input
3 2 3
1 2 3
0
1
2

Sample Output
2
3
1

Explanation
After the first rotation, the array becomes .
After the second (and final) rotation, the array becomes .
Let's refer to the array's final state as array . For each query, we just have to print the value of  on a new line:
1. , so we print  on a new line.
2. , so we print  on a new line.
3. , so we print  on a new line.

The best solution by me:
#include<stdio.h>
#include<stdlib.h>

int main(){
int n;
int k;
int q;
scanf("%d %d %d",&n,&k,&q);
int *a = malloc(sizeof(int) * n);
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
for(int a0 = 0; a0 < q; a0++){
int m;
scanf("%d",&m);
int index = (((m - k) %n )+ n) % n;
printf("%d\n", a[index]);
}

return 0;
}