Here are both Lithorian's and JaWiB's code, included together since they essentially used the exact same algorithm.
JaWib:
Code:
class JaWiB
{
public:
std::string originalNecklace(int numwhite, int numgold, int k)
{
int total=numwhite+numgold;
std::string ret;
ret.reserve(total); //reserve space for string
ret.assign(total,'w'); //fill string with w's
int h=1; //used to see if gold pearl needs to be added
for (int i=0,j=0;i<numgold;h++)
{
if (ret[j]=='g') //hit a gold pearl
{
--h;
if (++j==total) //skip this pearl
j=0;
continue;
}
if(h%k) //add a gold every k times; this is not a k time...
{
ret[j]='w';
}
else
{
ret[j]='g';
++i; //increment gold pearl counter
}
if (++j==total) //move on to next pearl, is it highest index?
j=0; //if so, go back to first pearl
}
return ret;
}
};
Lithorien:
Code:
class Lithorien
{
public:
std::string originalNecklace(int numWhite, int numGold, int k)
{
char *tArry = new char[numWhite + numGold]; // Dynamically allocate the char array.
// Initalize every array element to NULL.
for (int q = 0; q <= (numWhite + numGold); q++)
{
tArry[q] = '\0';
}
// Algorithm.
int x = 1, z = 0; // Counter for the inner for() loop, 'g' counter.
if (numGold > 0)
{
while (z < numGold) // While there aren't enough 'g's..
{
for (int y = 0; y < (numWhite + numGold); y++) // Go through the array..
{
if ((x == k) && (tArry[y] != 'g') && (z < numGold)) // If x is the next k, and the array ISN'T on a 'g' already..
{
tArry[y] = 'g'; // Make the array element g.
x = 1; // Make our 'counter' move back to 1.
z++; // Increment our 'g' counter.
}
else if (tArry[y] != 'g') // Assume w if not on a 'g' currently.
{
tArry[y] = 'w';
x++; // Increment our x.
}
// If the counter is on a g already, there's no need to do anything. So we skip it, and we don't update x. This lets us keep a constant 'k' without having to shift arrays.
}
}
}
else // If all whites are inputted, we need to handle that. Otherwise the program'd hang.
{
for (int r = 0; r < numWhite; r++)
{
tArry[r] = 'w';
}
}
// Return a string.
std::string s(tArry); // Make our string the char array. This is why we initalized to NULL - It ensures that this string will be null terminated. If we didn't, originalNecklace(9, 13, 11) would output garbage characters.
return(s);
}
};
Both produced correct results for every test case and more or less used the same algorithm I described above with only minor modifications. Both I give 10 points for correct solution, and + 2 snazzy points for nice concise algorithm. This was a tough call, but if we need a winner I'll award an extra .5 points to JaWib since his algorithm automatically handles the special case where there are no gold pearls.
