Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
ah sorry, marked as resolved
Mostly fixed!
Fixed!
I have never really understood bitwise operators, but I will try to look at them!
That's right
This solution is also in pseudo-polynomial time but it is optimized using bitwise operations, which makes it 64 times faster. Try to figure out why it works! :D
Well this sucks. Even the geeksforgeeks solution didn't pass in the given time constraints and it was in psuedo-polynomial time.
Just a quick question, the subset can be greater than two values correct? For example, the k value can be 9 and the subset is {1,3,5}.
This comment is hidden because it contains spoiler information about the solution
Thank you for your insight. Do you mind disclosing what kind of solution would work here?
I don't think a greedy solution would work here... Consider arr = [3,6,7,9] and K = 10, a subset would be {7,3}. Let's look at all the conditions in your for loop:
len(res) != 0, so the first condition fails
total != 0, so the second condition fails
total - res[-1] (10 - 9) > 0, so the third condition (if) fails
total - res[-1] (10 - 9) != 0, so the third condition (elif) fails
Now from your else, total = 10 - 9 = 1
Since there is no 1 in the original array, your code will loop through the array and incorrectly output False.
I reworked my solution but it still fails some test cases. Can anyone explain to me why? I thought it would be foolproof.
def hasSubsetSum(arr,k): res = sorted(arr) total = k if sum(arr) < k: return False if sum(arr) == k: return True for _ in range(len(arr)): if total - res[-1] < 0: if len(res) == 1: return False res.pop(-1) elif total - res[-1] == 0: return True else: total -= res[-1] res.pop(-1) return False
Random generator should be put in the test fixture, not in Preloaded.
The tests almost always expect the same result.
It is if you think it is.
Approving now.
Loading more items...