You are not logged in. Please login at to post your questions!



Can anyone tell me the suitable algorithm/approach to solve this problem

asked 05 Oct '14, 19:52

viperx's gravatar image

accept rate: 0%

edited 05 Oct '14, 19:54

I think this can be solved by sqrt decomposition in O(Q * M * log(N)) time where M = sqrt(N). The basic idea is to divide the given array into M blocks each of size M, Now we change each element a[i] to its prefix sum. Then a sum of range l...r is zero if and only if a[l - 1] == a[r]. Now each query range l...r can be covered by at most M blocks of size M and at most 2*M-2 trailing and leading elements. For each distinct element we can store all its occurrences at separate places and we can to binary search to find the right most elements which is less than or equal to r. Similarly we can do for each block we pre-process and store what is the answer for each right in O(N) so total of O(N * M) for M blocks and answer in O(1) for query on each block. And I also guess that we can remove the log(N) factor of binary search by doing offline programming.


answered 16 Nov '14, 01:17

adurysk's gravatar image

4★adurysk ♦
accept rate: 11%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 05 Oct '14, 19:52

question was seen: 4,640 times

last updated: 16 Nov '14, 01:17

Related questions