Delete And Score

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in company
Goldman Sachs

Problem statement

You are given an integer array ‘arr’ of size ‘N’. You need to perform the following operation any number of times.

1- Select a element arr[i] and add it to your score. 

2- Delete every element equal to arr[i] - 1 and arr[i] + 1.

Your task is to return the maximum possible score.

For example: 
You are given arr = {5, 6, 7, 8}. Then our answer will be 14. 

First select arr[1] = 6 and add it to your score. Score will be 6. Now, we also have to delete all elements equal to arr[1] - 1 = 5 and arr[i] + 1 = 7. 

In next move select arr[3] = 8. Delete it and add it to your score. Score = 14. Now, no element is left to be deleted. 

So, our final score is 14, which is the correct answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains an integer, ‘N’, denoting the size of the array.

The second contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output Format: 
For each test case, print a single integer, denoting the maximum score possible after performing the operation any number of times.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= N  <= 10 ^ 6
1 <= arr[i] <= 10 ^ 4

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
4
5 6 7 8
5
3 4 9 10 11
Sample Output 1:
 14
 24
Explanation:
For the first test case, 
First select arr[1] = 6 and add it to your score. Score will be 6. Now, we also have to delete all elements equal to arr[1] - 1 = 5 and arr[i] + 1 = 7. 

In next move select arr[3] = 8. Delete it and add it to your score. Score = 14. Now, no element is left to be deleted. 

So, our final score is 14, which is the correct answer.

For the second test case, 
You are given ‘arr’ = {3,4,9,10,11}. Then our answer will be 24.     

First select arr[1] = 4. Delete it and add it to your score. Score will be 4. Now, we also have to delete arr[1] - 1 = 3 and arr[1] + 1 = 5. Then arr = {9, 10, 11}.

In the next move select arr[0] = 9. Delete it and add it your score. Score = 13. Now, we also have to delete all elements equal to arr[0] - 1 = 8 and arr[0] + 1 = 10. Then arr = {11}.

Select arr[0] = 11. Delete it and add it to your score. Score = 24. Now, no element is left to be deleted. 

So, our final score is 24, which is the correct answer.
Sample Input 2:
2
4
1 6 4 9
5
4 4 7 9 10
Sample Output 2:
20
25
Hint

Try to use recursion.

Approaches (3)
Recursion

First, we will create a count array, where count[i] stores (total occurrences of i in arr). We can add all the occurrences of an element to our score because we only have to delete that particular element and all occurrences of (element - 1) and (element + 1). We have two choices for every element in count: to include this element in our score or exclude it. If we include this element, we can not take the previous element (element - 1) but can take (element - 2). So, we will select the choice at every move that will add maximum value to our score.
 

Algorithm:

  • Initialize a variable maxN with a value 10001
  • Initialize an integer array count of size maxN
  • For each element, num in arr
    • Increment count[num] by 1
  • return helper(maxN - 1, count)

 

  • Maintain a function helper(int num, int[] count)
  • If num is less than or equal to 0 
    • return 0
  • Otherwise return maximum of (helper(num - 2, count) + (count[num] * num)) and helper(num - 1, count)
Time Complexity

O(2^N), where N is the size of the input array.
 

At each recursive call, we are creating 2 recursive calls. For the N element, we are creating 2^N recursive calls. Hence, the overall time complexity is O(2^N).

Space Complexity

O(N). where N is the size of the input array.
 

The recursion stack requires O(N) space in the worst case. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Delete And Score
Full screen
Console