This is a hackerrank program which I tried last week. There is a list of Items in the shopping cart, each having a cost associated with it.

There are n items, the cost of the ith item is i dollars and m items have already been bought and represented in the array arr. Currently, there are k dollars, find the maximum number of distinct items one can have in total after purchasing any number of items from that money.

Example:

Consider n=10,m=3,k=10,arr=[1,3, 8]. 

So, the task is to find the maximum number of distinct items which can be purchased out 10 items within 10 dollars apart from items {1,3,8}. At max, 2 items can be purchased apart from the given 3 , let's say Item - 2 and Item - 5. Total cost=2 5=7, which is less than 10 .

Let us consider three items - Item - 2, Item - 4, 200,

The answer is 5 (3 already purchased, and 2 purchased just now).

The function must return an integer denoting the maximum count of distinct items that can be purchased.

The function has the following parameter(s):

n : an integer denoting the number of items arr[m]: an integer array denoting already purchased items
k : an integer denoting amount in dollars Constraints

Constraints -

1≤n≤10^6
1≤m≤10^5
1≤k≤10^9
1≤a[i]≤10^6

This question is already posted by someone here, just in case if anyone wants to look at the exact question.

Now, my thought process. As I have K dollars and I have to find the maximum elements to collect whose sum is up to k. I start a number from 1 till n and check if that number is missing in the input list, if yes then add to a sum, and do this process until the sum is less than or equal to k.

public int process(int n, int k, List<Integer> arr) {
    Set<Integer> set = new HashSet<>(arr);
    long sum = 0;
    int result = arr.size();
    for(int i=1; i<=n; i  ) {
        if(set.contains(i) == false) {
            if(sum   i <= k) {
                sum  = i;
                result  ;
            }
        }   
    }
    return result;
}

Now, this program works for the given sample test cases.

Some other test cases are:

n=5, k=8, arr=[3,6] . Expected answer = 5

n=8, k=5, arr=[1,2] . Expected answer = 3

n=1, k=10, arr=[1] . Expected answer = 1

My program works with these sample testcases. But hackerrank has 11 other hidden test cases which are all hidden that are failing with wrong result, i don't see any memory errors or time out errors for these hidden testcases.

Now my question is, what is the right approach to solve this problem? As the question says to find the maximum elements to collect, I started from 1 till n to find the missing elements which is valid approach but still it is failing.

CodePudding user response：

As you are asking about the right approach, I won't post a full code but give you some pointers. Feel free to tell me if it's not a good answer and I'll delete it.

1. Look at the constraints, and verify if an overflow is possible somewhere in your code
2. Your loop goes from 1 to n. Usually they go from 0 to n-1, maybe there is an off-by-one error somewhere ? Test with edge cases
3. You loop trough the whole range [1..n]. Is there a condition where you could stop earlier ?
4. The prices are in increasing order, maybe there is a general formula to compute the total price ? This could mean rethinking the whole algorithm, but you would gain a lot of time.

CodePudding user response：

I don't see any obvious error in your code. Is it possible that for the cases that failed (which I infer had a lot of data entry), you could have made an input error? As far as the possibility of overflow, the maximum value an int can hold is 2,147,483,647. From the problem description an int should be sufficient and you shouldn't need any long variables.

Anyway, I would suggest some changes:

1. Optimize the exit condition in the for loop within process to break when testing greater values of i in the for loop would be fruitless. This also results in a simplified loop body.
2. Change the interface to process slightly so that the caller only has to pass an Intger array; creation of the List<Integer> variable from this array will be done by process. Why should the caller know that creating a List is required from the problem description, which specifies only passing an array?

import java.util.*;

public class Test {
    public int process(int n, int k, Integer[] arr) {
        Set<Integer> set = new HashSet<Integer>(new ArrayList<Integer>(Arrays.asList(arr)));

        int sum = 0;
        int result = arr.length;
        // Never let i exceed n and once you have an i value
        // where the current sum   i exceeds k, you can stop:
        for (int i = 1; i <= n && sum   i <= k; i  ) {
            if (!set.contains(i)) {
                sum  = i;
                result  ;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Test t = new Test();

        Integer[] arr = {1, 3, 8};
        System.out.println(t.process(10, 10, arr));
    }
}

Prints:

5

CodePudding user response：

Could the key be the word distinct in the phrase "find the maximum number of distinct items"? What if the array contains duplicates? Try initializing result with

int result = set.size();

instead and see if it solves the problem.