f(f(n)) = -n

Originally from stackoverflow
While working on this puzzle, became confused, but this can be simplified if we first write the state diagram and then the code. The state diagram should consider odd/even and +ve/-ve numbers.
A simple control flow can be as follows:
A: 1 → 2
B: 2 → -1
C: -1 → -2
D: -2 → 1
E: 1 → 2

Notice that E and A are same.
Once we have this,

if n is +ve:
   if n is odd : return n+1
   if n is even : return -1* (n-1)
else if n is -ve:
   if n is odd : return n-1
   if n is even : return -1 * (n+1)

We get the highest rated solution on stackoverflow.

The Colored Socks

Ten Red socks and ten blue socks are all mixed up in a dresser drawer. The twenty socks are exactly alike except for their color. The room in in pitch darkness and you want two matching socks. What is the smallest number of socks you must take out of the drawer in order to be certain that you have a pair that match? (source: Entertaining Mathematical Puzzles By Martin Gardner, Anthony Ravielli)

Answer:


Many people (including me) initially (and incorrectly )solved this puzzle as follows:
* Initially I pull out a sock, and this could be Red / Blue.
* Then to match the color of the first sock, we pull out (10 + 1) socks.

But if we read the question carefully, it simply says, "pair that match" and nothing about the
color, so all we need is to pull out just three socks.

Transportation of Bananas

There are 2 cities A and B, dist. between them is 1000 Km
we have 3000 bananas in city A and a elephant can carry max 1000 bananas at
any given time and it needs to eat a banana every 1 Km.

How Many Max. No. of bananas one can transfer to city B?

Note : the elephant cannot go without bananas to eat.

One possible solution is to transport the banana in stages or intervals


for 200 kms we have,
A   200  B  200   C  200   D  200   E   200  F
|--------|--------|--------|--------|--------|

A to B
------
-> 2000, 800
<- 2000, 600
-> 1000, 1400
<- 1000, 1200
-> 0   , 2000

distance left = 800

B to C
--------
-> 1000, 800
<- 1000, 600
-> 0,    1400

distance left = 600

C to D
-------
-> 400, 800
<- 400, 600
-> 0,   800

distance left = 400

Move from D to F , leaving 400 bananas.


for, 250 kms we have,
A  250   B   250  C  250   D  250   E
|--------|--------|--------|--------|

A to B
------
-> 2000, 750
<- 2000, 500
-> 1000, 1250
<- 1000, 1000
-> 0   , 1750

distance left = 750

B to C
------
-> 750 , 750
<- 750 , 500
-> 0   , 1000

distance left = 500

Go directly from C to E (500 kms) leaving 500 bananas

for, 300, we have
A   300  B  300   C  300   D  100   E
|--------|--------|--------|--------|

A to B
-------
-> 2000, 700
<- 2000, 400
-> 1000, 1100
<- 1000, 800
-> 0,    1500

distance left = 700

B to C
------
-> 500, 700
<- 500, 400
-> 0  , 600

distance left = 400

travel C to E, leaving only 200 bananas

Using the above scheme, we can transport a max of 500 bananas for intervals of 250, 
this is probably not the best solution, and using dynamic programming we can find the
best solution.

sum of digits puzzle

Let the letters: A, B, C, D, E, F, G, H, and I be representative of the
numbers 1, 2, 3, 4, 5, 6, 7, 8, 9 in no particular order. If we let
A+B+C=C+D+E=E+F+G=G+H+I=13, then what must E be?

A + B + C
        +
        D
        +
        E + F + G
                +
                H
                +
                I

Answer:

start from the maximum value = 9
and it can only be combined with 1, 3
so we have,
(1, 3, 9)

take the second maximum value = 8
possible tuples,
(1, 4, 8)
(2, 3, 8)

take the third max value = 7
(1, 5, 7)
(2, 4, 7)

take the third max value = 6
( 2, 5, 6 )
( 3, 4, 6 )

now, only C, E, F are common,
so,

Option I:

9 + 3 + 1
        +
        8
        +
        4 + 7 + 2
                +
                5
                +
                6

This is a perfectly valid arrangement

Option II:

9 + 1 +[3]
        +
        8
        +
        2 + 7 + 4
                +
                6
                +
               [3]

which is an invalid arrangement

So the required answer is 4.

Trailing zeros in 100!

What is the trailing number of zeros in 100!

Just compute zeros in , n * 8 * 10
we choose 8 because that is the max even num, 
that produces the max num of zeros.
----------------------
                Zeros
----------------------
(5  * 8  * 10)  = 2
(15 * 18 * 20)  = 2
(25 * 28 * 30 ) = 3
(35 * 38 * 40)  = 2
(45 * 48 * 50 ) = 3
(55 * 58 * 60 ) = 2
(65 * 68 * 70)  = 2
(75 * 78 * 80 ) = 3
(85 * 88 * 90)  = 2
(95 * 98 * 100) = 3

crystal balls and the floor from which they break

There are two identical crystal balls and one needs to find out which is the maximum floor in a 100 storey building from where the balls can fall before they break. In the most efficient way, what will be the maximum number of drops required to find the right floor in any possible scenario? The balls are allowed to be broken (if required) while finding the right floor.


Solution 1 (Constant interval, not optimal):

import sys

min_drops = 100
min_interval = 1
for interval in range(1,50):
    drops = 100/interval + max(100%interval, interval-1)
    print "interval " , interval , " drops " , drops
    if drops < min_drops:
        min_drops = drops
        min_interval = interval

print "min_interval ", min_interval, " min_drops ", min_drops

Solution 2 (increasing interval, not optimal):
seq = (1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 100)
count(seq) = 14.
worst case = 14 + 8 = 22


Solution 3 (decreasing interval, optimal, best solution):
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 100

The advantage with decreasing interval is that, when the crystal ball breaks
the number of trails required to determine the floor at which it breaks gets
smaller everytime.,

One method to decrease the interval is to find a number n, such that
∑n >= no_of_floors,
and then start from interval n, n+n-1, n+n-2 , .... 100
so when the ball breaks at 100, the number of trails required is the difference
b/w previous floor and current floor.

we have ∑n = n(n+1)/2 >= 100
solving the above equation gives, n = 14
so we will test from:
#14, #(14 + 14 - 1 = 27), #(27 + 14 - 2 = 39), #(39 + 14 - 3 = 50), #(50 + 14 - 4 = 60), #(60 + 14 - 5 = 69), #(69 + 14 - 6 = 77), #(77 + 14 - 7 = 84), #(84 + 14 - 8 = 90), #(90 + 14 - 9 = 95), #(95 + 14 - 10 = 99), and finally from #100.

bit function

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Analysis:

Ex:
// series with 2 bits
00000011 1
00000101 2
00000110 3
00001001 4
00001010 5
00001100 6
00010001 7

// series with 3 bits
00000111 1
00001011 2
00001101 3
00001110 4
00010011 5

//------------- PROBABLY NOT SO OPTIMAL ---------------
#include "stdio.h"
#include "stdlib.h"

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}
/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

void FindInSeries(size_t k)
{
    const size_t bit_count = CountBits_O1(k);
    size_t seq_pos = 0;
    // This is the start of the series
    size_t start = ( 1 << bit_count ) - 1;

    printf(" start %d, bit_count %d \n", start, bit_count );

    for ( size_t i=start; i != k; ++i)
    {
        if ( CountBits_O1(i) == bit_count )
        {
            ++seq_pos;
            printf("%d ", i);
        }
    }

    ++seq_pos;

    printf("\n f(%d) = %d \n", k, seq_pos);
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    InitLookup();
    FindInSeries(num);
    return 0;
}

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;

}

Product Array

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

#include "vector"
#include "iterator"
#include "algorithm"
#include "iostream"
#include "stdlib.h"
using namespace std;

/*
 * Pass 1
   --->
   1 2 3 4 5
       ^
   Pass 2
         <--
   1 2 3 4 5
       ^
*/

void ArrayProduct(vector& array)
{
    const int n = array.size();
    vector product(n);
    int prod = 1;
    for ( int i=0; i    {
        product[i] = prod;
        prod *= array[i];
    }
    prod = 1;
    for ( int i=n-1; i>=0; --i)
    {
        product[i] *= prod;
        prod *= array[i];
    }

    copy ( product.begin(), product.end(),
            ostream_iterator(cout, " ")
         );
}

int main ( int argc, char* argv[])
{
    const int n = atoi(argv[1]);
    vector array(n);
    for ( int i = 1; i<= n; ++i )
        array[i-1] = i;
    ArrayProduct(array);
    return 0;
}