We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Absolute Element Sums
  5. Discussions

Absolute Element Sums

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 58 Discussions, By:

votes

Please Login in order to post a comment

  • ayushr2
    5 years ago+ 5 comments

    I have a fairly simple solution which passes all test cases. However, I fail to see how this question requires a search algorithm. The suggested topics included Binary Search but how do I incorporate binary search in this?

    here is my DP solution.

    n = int(input())
    arr = list(map(int, input().split()))
    
    q = int(input())
    queries = list(map(int, input().split()))
    
    count = [0]*4001
    for i in arr:
        count[2000 + i] += 1
        
    sum_num_right = []
    sum_num_right.append(n)
    for i in range(4000):
        sum_num_right.append(sum_num_right[i] - count[i])
    
    sum_right = [0]*4001
    for i in range(4001):
        sum_right[0] += count[i] * i
        
    for i in range(1,4001):
        sum_right[i] = sum_right[i - 1] - sum_num_right[i]
        
    sum_left = [0]*4001
    for i in range(4000, -1, -1):
        sum_left[4000] += count[i] * (4000 - i)
        
    for i in range(3999, -1, -1):
        sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
        
    acc = 0
    for i in queries:
        acc += i
        mid = 2000 - acc
        if mid < 4001 and mid >= 0:
            print(sum_right[mid] + sum_left[mid])
        elif mid < 0:
            print(sum_right[0] + n * abs(mid))
        else:
            print(sum_left[4000] + n * (mid - 4000))
    
    5|
    Permalink
    View more Comments..
  • jacobjoh
    7 years ago+ 4 comments

    the editorial says there is a O(logN) solution but that is impossible when you have to process Q sums. The complexity must have a variable for Q. I found a O(NlogN) + O(QlogN) algorithm but it only gets the test cases right up to #5 and times out for the last three cases. Is there a faster solution than O(NlogN) + O(QlogN)?

    4|
    Permalink
    View more Comments..
  • xcabel
    6 years ago+ 0 comments

    o(qlogn) is good enough. You need to consider the partial sum of the queries x instead of x and binary search for the index around which the sign is flipped after influence of this partial sum of x

    3|
    Permalink
  • simomo
    6 years ago+ 2 comments

    I had fun solving this with C in 45 lines by calculating two constant sized tables before seeing any Q's and after that I'm just doing array lookups using the sum of all Q's so far. So my space is O(1) and time O(Q + N), and I did get rid of the 4001'ish Q multiplier in time as well which few people mentioned; I had that version at first too, but it failed the last two tests :)

    3|
    Permalink
  • echan3960
    3 years ago+ 0 comments

    For people stuck on test cases 6 and above, in java the results requires numbers above the MAX_VALUE of int. So it is necessary to change the returning array to long and change the "result" array in the main function to long[]. After I changed that i solved everything besides test case 12 which timed out which i eventually solved.

    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature