n.j.joshi
BAN USERLet's say i'th and j'th element in the array are p and q, respectively . What we want is
i + j = p + q
or
i - p = - (j - q)
O(n) algorithm:
1. walk over the array and do
a[i] = a[i] - i
2. Again walk over the array
h = hashMap
for every A[i]:
if -A[i] in h :
return true;
else
insert A[i] -> h
Here is some code for nextSmallest integer with the same number of set bits
int nextSmallest(int n) {
int scanner = 0;
// find the first set bit in n
while ( !((n >> scanner)&1) ) {
scanner++;
}
// now skip block of consequtive 1's
while ( (n >> scanner)&1 ) {
scanner++;
}
// position to the MSB of the block of 1's
scanner--;
// reset the bit
n &= ~(1 << scanner++);
// now find the first clear bit in n
while ( (n >> scanner)&1 ) {
scanner++;
}
// set the bit
n |= (1 << scanner);
return n;
}
This can be solved in O(n) time. I think my solution in principle matches with the topological sorting idea.
The idea is to observe that the exact ranking of a student does not matter, but with respect to his next neighbors (whose candies in turn are decided by their next neighbors, and so on). So, it is sufficient to give the number of candies to a student, equal to maximum of the lengths of ever decreasing contiguous subsequence (of rankings) on his/her left and to his/her right, counted starting from him. Here "strictly increasing" or "strictly decreasing" is very import ant to minimize the candies.
Example: for students lined-up according to the rankings 1, 3, 3, 4, 5, 4, 3, 1
the third student has no other students on his left with ever decreasing rankings (starting from him) and no students on his right, so he receives max(0, 0) + 1(minimal candy) = 1 candies, and so on.
The algorithm does exactly the same:
1. let fromLeft[i] and fromRight[i] be the arrays holding lengths of ever decreasing contiguous subset including i'th element on left and right,
2. traverse the rankings from left to right and fill up fromLeft, with the formula
fromLeft[i] = fromLeft[i-1] + 1;
whenever ranking[i-1] < ranking[i]
3. traverse the rankings from right to left to similarly setup fromRight
4. The candies to a student at position i is
candies[i] = max{fromLeft[i] , fromRight[i]} + 1; // 1 for the minimal candy
5. output the sum in candies
Step 4 and 5 can be combined (as done in the code below). One does not need to save number of candies to each person, if only the minimal is required, saving O(n) space
// Calculate minimal number of candies required
int getMinimalCandies(const std::vector<double>& rankings, std::vector<int>& candies){
// number of students
int numStudents = (int) rankings.size();
// ever decreasing contiguous subsequence
// from every position to its right (left)
std::vector<int> onLeft(numStudents, 0), onRight(numStudents, 0);
// for each position, determine ever decreasing
// seq. on the left and on right
for (int i = 0; i < numStudents; i++) {
// if the ranking on immediate left was
// higher than this one
if (i && // don't do it for i = 0
rankings[i-1] < rankings[i]) {
// length of subsequence at this
// position is one more than the previous one
onLeft[i] = onLeft[i-1] + 1;
}
// similarly for decreasing ranking seq. on right
if ( (((numStudents - 1) - i) < numStudents - 1) &&
rankings[((numStudents - 1) - i) + 1] < rankings[(numStudents - 1) - i]) {
onRight[(numStudents - 1) - i] = onRight[((numStudents - 1) - i) + 1] + 1;
}
//
}
// candies to be given to every child is
// max-length(increasing seq. on left, decreasing seq. on right)
int totalCandies(0);
for (int i = 0; i < numStudents; i++){
candies[i] = std::max(onLeft[i], onRight[i]) + 1;
totalCandies += candies[i];
}
// return total number of candies to be distributed
return totalCandies;
}
// API, from main
std::cout << "The total number of minimal candies required are " << getMinimalCandies(rankings, candies) << std::endl;
// print individual candies (optional)
std::cout << "Distribute as ";
for (int i= 0; i < n; i++)
std::cout << candies[i] << "\t";
std::cout << std::endl;
simply because `char` always takes one byte, the basic unit of computer word (or world) :).
- n.j.joshi February 24, 2014