0

I am pretty noobie with C++ and am trying to do some HackerRank challenges as a way to work on that.
Right now I am trying to solve Angry Children problem: https://www.hackerrank.com/challenges/angry-children

Basically, it asks to create a program that given a set of N integer, finds the smallest possible "unfairness" for a K-length subset of that set. Unfairness is defined as the difference between the max and min of a K-length subset.

The way I'm going about it now is to find all K-length subsets and calculate their unfairness, keeping track of the smallest unfairness.

I wrote the following C++ program that seems to the problem correctly:

#include <cmath> #include <cstdio> #include <iostream> using namespace std; int unfairness = -1; int N, K, minc, maxc, ufair; int *candies, *subset; void check() { ufair = 0; minc = subset[0]; maxc = subset[0]; for (int i = 0; i < K; i++) { minc = min(minc,subset[i]); maxc = max(maxc, subset[i]); } ufair = maxc - minc; if (ufair < unfairness || unfairness == -1) { unfairness = ufair; } } void process(int subsetSize, int nextIndex) { if (subsetSize == K) { check(); } else { for (int j = nextIndex; j < N; j++) { subset[subsetSize] = candies[j]; process(subsetSize + 1, j + 1); } } } int main() { cin >> N >> K; candies = new int[N]; subset = new int[K]; for (int i = 0; i < N; i++) cin >> candies[i]; process(0, 0); cout << unfairness << endl; return 0; }

The problem is that HackerRank requires the program to come up with a solution within 3 seconds and that my program takes longer than that to find the solution for 12/16 of the test cases. For example, one of the test cases has N = 50 and K = 8; the program takes 8 seconds to find the solution on my machine. What can I do to optimize my algorithm? I am not very experienced with C++.

Improve this question
1
  • Have you thought of sorting the array? Than the numbers are in intervals and you just have to look at the array of N once. You could also jump by steps of K to make the algorithm even faster. Assuming you sort in O(nlog n) and iterate in O(n), you'll do the job in O(nlogn) without regarding all N^K possible combinations. Commented Nov 17, 2014 at 7:02

2 Answers 2

Reset to default
1

All you have to do is to sort all the numbers in ascending order and then get minimal a[i + K - 1] - a[i] for all i from 0 to N - K inclusively. That is true, because in optimal subset all numbers are located successively in sorted array.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

much simpler way of thinking about the problem, thanks!
1

One suggestion I'd give is to sort the integer list before selecting subsets. This will dramatically reduce the number of subsets you need to examine. In fact, you don't even need to create subsets, simply look at the elements at index i (starting at 0) and i+k, and the lowest difference for all elements at i and i+k [in valid bounds] is your answer. So now instead of n choose k subsets (factorial runtime I believe) you just have to look at ~n subsets (linear runtime) and sorting (nlogn) becomes your bottleneck in performance.

Improve this answer

1 Comment

FunkyCat beat you by a few minutes, but that's what I ended up doing

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.