Missing Money

It is a dark and stormy night when three travelers must stop in hotel.
They approach the front desk, where the front desk clerk informs them of
the rate of $30 for three men in one room. The men each hand over a $10
bill for a total of $30. They are given a key and go to their room.
Moments later, the manager is informed of the transaction and reprimands
the clerk, reminding him of the 3 men/1 room special of $25 a night. The
manager asks the clerk to refund the $5 to the men. Taking five $1 bills
from the register, he goes to the men's room and knocks on the door.
While he waits for the men to come to the door, he realizes a problem.
How can he divide the 5 $1 bills evenly among the men? When they answer
the door, he tells them that there was a special that night and that the
total bill only came to $27. He gave them each $1 as a refund, and the
sneaky clerk made off with $2 for himself. Though it seems everyone came
out a winner, a problem occurs. In the beginning, $30 was paid. In the
end, however, the man had paid a collective $27, and the clerk had $2.
$27 + $2 =$29, not $30. The question is: where is the extra dollar?

Possible answer:

The Question itself is probably wrong, another way to look at it is,
The rent of the room is 25$, each three men contributed 9$, and 2$ was tips.

Pythagorean triplets in an array

Given an array print all the pythagorean triplets.

Answer:


See also : http://en.wikipedia.org/wiki/Pythagorean_triples#Elementary_properties_of_primitive_Pythagorean_triples

#include <vector>
#include <iterator>
#include <algorithm>
#include <stdio.h>
#include <iostream>
using namespace std;


/**
 * See 
 * we can make use of the properties to check that a pythagorean triplet is possible
 * */
bool IsPyTripletPossible(size_t a, size_t b, size_t c)
{
    bool flag = false;
    /*
     * # Exactly one of a, b is odd; c is odd.
     * */
    flag =  (a % 2) + (b % 2) ;
    if (!flag) return flag;
    flag = ((c%2) == 1);
    if (!flag) return flag;
    /*
        # Exactly one of a, b is divisible by 3.
        # Exactly one of a, b is divisible by 4.
        # Exactly one of a, b, c is divisible by 5.
    */
    if ( !(
             ( !(a%3) && (b%3) ) ||
             ( (a%3) && !(b%3) )
            )
       )
        return false;
    if ( !(
             ( !(a%4) && (b%4) ) ||
             ( (a%4) && !(b%4) )
            )
       )
        return false;
    // other tests ignored.
    return true;
}

void PrintPythagorousTriplets(vector &a)
{
    size_t i = 0, j = 1, k = 2;
    size_t lower_bound = 0;
    sort( a.begin(), a.end() );
    while ( k < a.size() )
    {
        if ( (a[k]%2) == 0  )
        {
            // RULE:
            // the hypotenuse cannot be a even number
            ++k;
        }
        else
        {
            size_t k_sq = a[k] * a[k];
            i = lower_bound;
            j = k - 1;
            bool found = false;
            while ( i < j )
            {
                size_t sq = a[i]*a[i] + a[j]*a[j];
                if ( sq == k_sq )
                {
                    printf(" %d, %d, %d \n", a[i], a[j], a[k]);
                    found = true;
                    break;
                    // break, because there can be one and only one
                    // py triplet, (because there is only one way to draw
                    // a triangle)
                }
                else if ( sq < k_sq )
                    ++i;
                else if ( sq > k_sq )
                    --j;
            }
            if ( found )
            {
                // RULE :
                // There are no Pythagorean triplets in which the hypotenuse and 
                // one leg are the legs of another Pythagorean triple.
                // so the next search can start from the hypotenuse of the current 
                // triplet
                lower_bound = i;
            }
            ++k;
        }
    }
}

int main( int argc, char* argv[] )
{
    if ( argc == 1 ) return 0;
    else
    {
        vector a(argc-1);
        for ( int i = 1; i <= argc-1; ++i)
            a[i-1] = atoi(argv[i]);
        cout << "Input :" << endl;
        copy ( a.begin(), a.end(), ostream_iterator(cout, " "));
        cout << endl;
        PrintPythagorousTriplets(a);

    }
    return 0xabcdef;

}

Add numbers in base n

Give an approach/code to add numbers in base n.

Answer:

After adding each digit, the sum%n will appear in the sum, and sum/n will be carried forward.