ksb_451's blog

quesition from sprinklr and makemytrip OA last year. can some one help?
By ksb_451, history, 3 years ago, In English

Given an integer N and an array containing N elements. Also given an integer Q denoting the number of queries. Query consist of three integers, T, X and Y. T denotes the query type and can take values 0 and 1. X denotes the starting position of the query. Y denotes the increment in position. Type 0 is for addition and Type 1 is for multiplication. For eg: Given N = 5,

arr[] = 1 2 3 4 5

Q=2,

0 2 2

1 1 3

For first query, T=0, X=2, Y=2. So we have to return sum of arr[X] + arr[X+Y] + arr[X+2Y] till end of array. Here it would be arr[2] + arr[4] = 3+5=8

For second query, T=1, X=1, Y=3. So we have to return product of arr[X] * arr[X+Y] * arr[X+2Y] till end of array. Here, arr[1] * arr[4] = 2 * 5 =10

As the answer can be large, return ans modulo 10^9+7.

N,Q <= 10^5

arr[i] <= 10^9

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ksb_451 (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

If $$$y > \sqrt{n}$$$, use brute-force. It will take $$$\mathcal{O}(\sqrt{n})$$$ per query. Otherwise, precalculate the answers for each $$$1 \le x \le n$$$ and $$$1 \le y \le \sqrt{n}$$$ using a simple dp. It will take $$$\mathcal{O}(n \sqrt{n})$$$.

Overall complexity: $$$\mathcal{O}((n + q)\sqrt{n})$$$

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A similar problem — Given an array and a bunch of queries, for each query we are given two numbers p and k. We start from index p and jump to index p+a[p]+k, and then make similar jumps again till we reach the end of the array. Find the number of steps we take for each query. This is an old codeforces problem. Solution is similar to the one described by "YouKn0wWho" above.

→ Reply