CareerCup

I think I partly understand what he wanted to say:
if the order of matrix multiplications is fixed, we can find an optimal factorization of the matrix product to minimize the # of arithm ops using DP algorithm:

h t t p://en.wikipedia.org/wiki/Chain_matrix_multiplication

though I am not sure how this relates to class diagrams / inheritance etc..

just to add more explanations: containment is used when the outer object needs to modify the behaviour of the inner object.

for the second part of the question: when the outer object dies, the contained inner object is also destroyed (since its not exposed to the outer world)

while in case of aggregation, it's not necessarily true:
you just decrease a reference counter since same object can be aggregated by other objects as well

the point is we need to associate the coefficients at equal powers of 'x' of both polynomials. Suppose the input polynomials are given as maps:
'coeffs_f' and 'coeffs_g' of the form:

monomial_degree -> coefficient

then polynomial addition can be done as follows:

// loop through all non-zero monomials of 'f'
foreach idx from coeffs_f do
res[idx] = coeffs[idx]
if coeffs_g.find(idx) then
res[idx] += coeffs_g[idx];
*mark* coeffs_g[idx]
end if
end do

// loop through the remaining non-zero monomials of 'g'
foreach idx from coeffs_g do
// skip if coeffs_g[idx] is already there
if *marked* coeffs_g[idx] then continue
res[idx] += coeffs_g[idx];
end do

Additionally, using a map is more convenient because with a linked list you do not have direct access to polynomial coefficients (need to scan the whole list first)

Abhishek is actually right: this technique is called "binary splitting": imagine if you wish to compute factorial of a large number, then performing arithmetic on balanced operands (ie of comparable size) is more efficient than computing x! in a usual way

also to give a hint how to reduce the # of muls, observe that we can remove the power-of-two factors from the factorial expression and combine the remaining ones according to multiplicity:

e.g.: 10! = 2^8 * ( 1 * 3 * 1 * 5 * 3 * 7 * 1 * 9 * 5) =
2^8 * (3 * 5)^2 * 7 * 9

hence we need to perform 4 multiplications instead of 8..

I think the best way to store sparse polynomials is by using a map (exponent vector)
Thus for addition one has go through all nonzero coeffs of both polynomials

when a matrix is non-square, we might run into loops when swapping the elements..
the following soln works:
1. assume matrix is stored as 1D array
2. for each element in the resulting (transposed) matrix, say its index is 'k', find the index of a corresponding element in the original matrix, say it's 'j'
3. if j > k then swap(a[j], a[k])
4. otherwise we should "follow the loop" since element in the location 'j' has
already been swapped

I hope my obscure explanations are understandable ))

here is the code:

// in:  n rows; m cols
// out: n cols; m rows
void matrix_transpose(int *a, int n, int m) {
    int i, j;
    printf("\nin: %d x %d\n", n, m);
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) 
            printf("%d ", a[i*m + j]);
        printf("\n");
    }
    for(int k = 0; k < n*m; k++) {
        int idx = k;
        do { // calculate index in the original array
            idx = (idx % n) * m + (idx / n);
        } while(idx < k);
        std::swap(a[k], a[idx]);
    }
    printf("\nout: %d x %d\n", m, n);
    for(i = 0; i < m; i++) {
        for(j = 0; j < n; j++)
            printf("%d ", a[i*n + j]);
        printf("\n");
    }
}

int main() {
    int n = 2, m = 8; // n rows, m cols
    int a[] = {1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4};
    matrix_transpose(a, n, m);
    return 1;
}

huh you are right..
ok let me rephrase the question: compute a factorial in the most efficient way (with the minimum no of arithmetic ops).
i.e. can we reduce the # of multiplications ?

preliminary version:

there is a one-to-one correspondence between k-permutations of 'n' elements and falling factorial (FF-) numbers with 'n-1' digits
where only 'k' leading digits can be non-zero.

For example, an FF-number X with 5
digits {a0, a1, a2, a3, a4} is defined as:

X = a0 + 5*a1 + 5*4*a2 + 5*4*3*a3 + 5*4*3*2*a4

subject to conditions:

a0 < 5, a1 < 4, a2 < 3, a3 < 2, a4 < 1

or, equivalently, this is a number in a mixed radix system where
the base vector is given by [5, 4, 3, 2, 1]

Then, to convert a permutation of 'n' elements to an FF-number,
we do the following:
for each element a[i] of a permutation (except the last one) count the number of elements 
with indices to the right of 'i' that are less 
than a[i]

Example (permutations of 5 elements):
permutation -> FF-number

[5 3 2 1 4] -> [4 2 1 0]
[1 2 5 3 4] -> [0 0 2 0]
[2 4 3 5 1] -> [1 2 1 1] etc.

Now, suppose we wish to generate 3-permutations of [1 2 3 4 5 6]
in lexicographical order. For this we consider all FF-numbers with 5 digits
for which *only 3 leading digits can be non-zero*

We start with: [0 0 0 0 0] which corresponds to the first permutation:
[1 2 3 4 5 6] taking a length-3 prefix of the latter one yields [1 2 3]

and continue in this way:

FF-number -> [3-permutation][remaining part]
[0 0 0 0 0] -> [1 2 3][4 5 6]
[0 0 1 0 0] -> [1 2 4][3 5 6]
...
[2 1 2 0 0] -> [3 2 5][1 4 6]
[2 1 3 0 0] -> [3 2 6][1 5 6]
[2 2 0 0 0] -> [3 4 1][2 5 6]
...
[5 4 2 0 0] -> [6 5 3][1 2 4]
[5 4 3 0 0] -> [6 5 4][1 2 3]

yeah that's what I mean: C(n,k) denotes the number of ways to choose a subset of 'k' elements out of 'n'

I can only show it on an example..
Suppose we have n = 5 and k = 3. Than we can encode any solution
of the above system as a particular subset of 5 elements out of 7
in the following way:

5 = 4 + 1 + 0 -> 1111010
5 = 2 + 2 + 1 -> 1101101
5 = 3 + 2 + 0 -> 1110110
5 = 1 + 1 + 3 -> 1010111
5 = 1 + 0 + 4 -> 1001111
5 = 0 + 5 + 0 -> 0111110
and so on, thus it should give C(n+k-1,n) eventually

ps. your recurrence is definitely correct, it's easy to check

@Achintya: just to develop your idea further

1. remove integral part
2. use two arrays 'col_sums' and 'row_sums' to keep the sums of fractional parts along each column and row, resp.

in your example above:
row_sums = [1, 1, 2]
col_sums = [2, 1, 1]

now the problem reduces to finding a matrix A[i][j] of 0's and 1's where the column and row sums agree with the above arrays. There are many solutions possible.

For our example, we might have:
1 0 0 = 1
1 0 0 = 1
0 1 1 = 2
----------
2 1 1

or

0 1 0 = 1
1 0 0 = 1
1 0 1 = 2
----------
2 1 1

and so on. In fact we can put 1 at any position in the matrix as long as the row/col sums are preserved.

To make a deterministic algorithm out of this, we can use the following simple procedure (A[i][j] is the resulting matrix):

for(i = 0; i < n; i++) { // process each row
  for(j = 0; j < row_sums[i]; ) { // place required # of 1's in row 'i'
     if(col_sums[j] == 0) // all "slots" in this column are occupied
        continue;
     A[i][j] = 1;
     col_sums[j]--; j++;
  }

I think it should be: F(n,k) := C(n+k-1,n)
.. not entirely sure though

that's the good one ))
this recursion looks pretty much like combinations
where we have C(n,k) = C(n-1,k-1) + C(n-1,k)

so I suppose we can reduce it to C(N,K) finally..

thanks @jingtianjiang, good point
well, computing \sum a[i]^n would certainly be an overkill. Yet perhaps this is a right direction to the solution.. Additionally, if you combine the above idea with xor test, it'd be quite hard to break

the number of subsets of [1..n] whose sum is 's'
is given by the coefficient of x^s in the polynomial:

F:=(1+x)*(1+x^2)*...*(1+x^n).

Example: n = 5
F:= 1+3*x^5+2*x^4+3*x^9+2*x^3+3*x^8+
3*x^7+2*x^12+x^2+3*x^6+2*x^11+3*x^10+x^14+x+x^13+x^15

thus the # of subsets which 
sum up to 3 is 2 (because F has a term 2*x^3)
sum up to 7 is 3 (F has a term 3*x^7)
sum up to 13 is 1 (F has a term x^13)
and so on..

we can compute the coeffs of F using 'shift-and-add'
approach, that is, start from (x + 1)
then shift this by 2 positions to the right and sum up
with the original coeffs: which is the same as multiplication by (x^2 + 1), and so on

I think it's not even needed to get rid of zero elements.
To check if two arrays are permutations of one another, we do the following steps:

1. find & compare min/max for arrays (if not equal we are done)
2. compare the sums: a[1]+...+a[n] and b[1]+...+b[n]
3. compare the sums of squares: a[1]^2+...+a[n]^2 and b[1]^2+...+b[n]^2

if all three conditions are fulfilled, the arrays are permutations
I'd appreciate if someone could find a counterexample

ok, folks, all your counterexamples contain zero element.
Do get rid of it, we can first count the # of zeros in each array,
if they are not equal, we are done.

If yes, we proceed with xor/add/mul tests as above where zero elements are not taken into account.

@Ashish Kaila: that's right if we assume to have an fp number with
very large mantissa (e.g., BigFloat).
Remember that, in floating-point format, any number is stored
in scientific format, i.e.:

sign * mantissa * 2^{exponent + bias}

each multiplication by 10 introduces some small error and
these errors tend to accumulate. Thus, comparing two fp-numbers
for equality is, in many cases, meaningless. Just try to run your
algorithm for n = 1.000002

you are right, sorry I've just chosen the wrong examples
but the rules are correct. It should be:

35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35972 -> 36063 (increment and mirror the upper half)
99999 -> 100001 (special case)

anyway it does not make the algorithm wrong

yeah there are basically 4 rules to find the next palindrome.
They can best be described using examples:

num -> next palindrome
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35911 -> 36063 (increment and mirror the upper half)
99965 -> 100001 (special case)

hence, what we need to do is just to check all of them in the order they listed above. The code is as follows:

// finds a smallest palyndrome number x2 > x
int next_palyndrome(int x) {
    int digits[12], n, x2 = x;
    for(n = 0; x2 != 0; n++) {
        digits[n] = x2 % 10;
        x2 /= 10;
    }
    int n2 = n / 2, n2p1 = n2 + (n & 1);
    // first try replacing the lower digits with rev upper digits
    int rev_hi = digits[n2p1], exp = 10;
    for(int i = 1; i < n2; i++) {
        rev_hi = rev_hi * 10 + digits[n2p1 + i];
        exp *= 10;
    }
    int hi = x / exp, lo = x % exp; // extract lower and upper halves
    x2 = hi * exp + rev_hi;
    if(x2 > x)     // CHECKING RULE 1
        return x2;
    hi += 1; // increment 'hi' and construct the number again
    if(hi == exp) { // handle a special case when hi = '99...99'
        if(n & 1) { // here we return: 100..001
            x2 = hi * exp * 10 + 1;  
        } else {
            x2 = hi * exp + 1;
        }
        return x2; // CHECKING RULE 4 
    }
    int t = (n & 1) ? hi / 10 : hi; // divide out a middle digit if necessary
    rev_hi = t % 10;
    // calculate the reverse of 'hi' again
    for(int i = 1; i < n2; i++) {
        t /= 10;
        rev_hi = rev_hi * 10 + (t % 10);
    }
    x2 = hi * exp + rev_hi;
    return x2;  // RULE 2 and 3 (together)
}

int main() {
    int x = 4992734;
    while(1) {
        printf("next: %d\n", x);
        int x2 = next_palyndrome(x);
        if(x2 <= x) {
            printf("FATAL: %d %d\n", x2, x);
            break;
        }
        x = x2;
    }
    return 1;
}

sample output:

next: 4992734
next: 4992994
next: 4993994
next: 4994994
next: 4995994
next: 4996994
next: 4997994
next: 4998994
next: 4999994
next: 5000005
next: 5001005
next: 5002005
next: 5003005
next: 5004005
next: 5005005
next: 5006005
next: 5007005
next: 5008005
next: 5009005
next: 5010105
next: 5011105
next: 5012105
next: 5013105
next: 5014105
next: 5015105
next: 5016105
next: 5017105
next: 5018105
next: 5019105
next: 5020205
next: 5021205
next: 5022205
next: 5023205
next: 5024205
next: 5025205

here the point is what policy we use to define which appointments are conflicting.
there are at least two options:
1. minimize the time interval between two scheduled appointments
2. maximize the total number of scheduled appointments

I guess the last option is more "fair" in a sense that we prefer to have many short
appointments instead of just a few long ones

this problem can be solved by greedy alg in O(nlogn) time.
first sort the appointments by increasing finishing times:
suppose f[1] <= f[2] <= ... <= f[n]

then run the following alg:
A = {1} // the first appointment
j = 1;
for i = 2 to n do
if s[i] >= f[j] then
A = A + {i} // add appointment 'i'
j = 1
end if
end do

accordingly all conflicting are those that are not in A

in linux you can set limits in your bash_profile using 'ulimit' command, i.e.:

ulimit -s : maximum stack size
ulimit -t : maximum size of page-locked memory
ulimit -d : maximum size of process' data segment (for mallocs)
etc.

there is also a variable-byte coding scheme where an integer
is represented in the following way:

7 least significant bits of each byte are taken from the original
integer, then the highest 8th bit is set to 1 if the number has
further non-zero bytes and is 0 otherwise

in such a way a 32-bit integer '200' would occupy just 2 bytes instead of 4.
This method gives a good compression if numbers represented have different magnitudes and allows us to store variable-length integers

iterator design is rather simple: you define a concept which is basically the set of typenames custom iterators should provide
to be eligible as input iterators. Then you also define
iterator_traits to distinguish between C-style pointers and
iterator objects, smth like:

template <class T>
struct iterator_traits { // forward definitions from iterator type T
typedef typename T::data_type data_type;
typedef typename T::ref_type ref_type;
...
};
template <class T>
struct iterator_traits<T*> { // same for pointers
typedef T data_type;
typedef T& ref_type;
...
};

good algo @eugene ))

I think what you are doing is just sorting the array by bit-reversal: indeed because first you partition mod 2
than mod 4 and so on. This can be done in a single pass, if the numbers are small, or using a conventional sort as follows:

struct cmp {
    bool operator()(int a, int b) {
        return (bitrev(a) < bitrev(b));
    }
    int bitrev(int x) {
        int m = 0x55555555;
        x = ((x & m) << 1) | ((x & ~m) >> 1);
        m = 0x33333333;
        x = ((x & m) << 2) | ((x & ~m) >> 2);
        m = 0x0f0f0f0f;
        x = ((x & m) << 4) | ((x & ~m) >> 4);
        m = 0x00ff00ff;
        x = ((x & m) << 8) | ((x & ~m) >> 8);
        m = 0x0000ffff;
        x = ((x & m) << 16) | ((x & ~m) >> 16);
        return x;
    }
};

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
    int n = sizeof(a) / sizeof(int);
    // get a random shuffle first
    std::random_shuffle(a, a + n);
    for(int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
    // now sort the array according to bit rev index
    std::sort(a, a + n, cmp());
    for(int i = 0; i < n; i++) {
        std::cout << a[i] << " ";
    }
    std::cout << "\n";
    return 0;
}

output: 1 9 5 3 11 7 8 4 12 2 10 6

we need to find and print out all 13th days of a month which fall on Friday (starting from 01.01.1900)

what about this one, works for types and variables:

#define SIZEOF_type(T) \
        ((char *)((typeof(T) *)0 + 1))

yep, you are right ))
But you agree that the only possible application of this is to align data properly.. So the question should be: find a nearest multiple of 8 that is not smaller that then current number

well, this is a standard trick to get your
data aligned by double-word boundary, i.e.: (x + 7) & ~7

that's good one))

well, that's division by 2 )) can be replaced by bitshifts

subtracting is not very efficient if the divisor much smaller than the dividend
you can adapt the binary search for this problem,e.g:

// computes a = b*q + r with 0 <= r < b
void divide(unsigned a, unsigned b, unsigned& quo, unsigned& rem) {
    // suppose numbers are positive
    if(a < b) {
        quo = 0; rem = a;
        return;   
    }
    quo = 1;
    while(quo*b*2 <= a) {
         quo *= 2;
    }
    // here it holds that: quo*b <= a < quo*b*2
    if(quo * b == a) {
        rem = 0;
        return;
    }

    unsigned ql = quo, qr = quo*2, mid;
    while(1) {
        mid = (ql + qr) / 2;
        if(mid*b <= a && a < (mid+1)*b)
            break;
        if(mid*b < a) {
            ql = mid+1;
        } else {
            qr = mid;
        }
    }
    quo = mid, rem = a - quo * b;
}

int main() {
    unsigned a = 2556721331, b = 13, q, r;
    printf("correct: %d %d\n", a / b, a % b);
    divide(a, b, q, r);
    printf("test: quo: %d; rem: %d\n", q, r);
    return 1;
}

nice algo! small improvement is that you also have to take care
of boundary cases, i.e.,
if you search for '2' in {5,4,3,2,1}, the index i can become
negative, this can be fixed as follows:

for (i=0; i<arr.length;)
{
   if (arr[i]==p)
   {found = 1;
    break;
   }
   i += abs(p - arr[i]);
}

@devanharikumar89: you said that this problem should be solvable
by pensil-and-paper ?

meaning that there is a simple formula for the number of solution
do you remember what was the answer ?
I suspect it should be: 21*22*23 = 10626 ?

'id=9783960' it's a different problem.
Here it is asked to find a SUBARRAY (contiguous part) that can be transformed to a sequence of consecutive integers, i.e.:

a = {4,5,1,5,7,4,3,6,3,1,9}
the subarray is: {5,7,4,3,6} because these numbers can be arranged as: {3,4,5,6,7}

correct: that's why I use hash_map instead of simple array

well, as I said we either have a parent pointer then the solution of anonymous above works, otherwise we must have access to the root, then my solution works

nope this is a brilliant idea ! you just needed to develop it further.

your logic is correct: what we need is to transpose an M x 3 matrix stored in a row-major manner using in-place algorithm.
The main difficulty is that in-place algorithm generates
loops during permutations..

Discussions be found here: en.wikipedia.org/wiki/In-place_matrix_transposition

// merge sort: returns a pointer to the head of a sorted list
list *merge_sort(list *head) {
    if(head == 0)
        return 0;
    list *p = head, *pp = p, *prev = 0
    if(p->next == 0)
        return head; // already sorted
    // find a split in the middle using two ptrs
    while(pp != 0 && pp->next != 0) {
        prev = p, p = p->next;
        pp = pp->next->next;
    }
    prev->next = 0; // cut the list in the middle
    list *h1 = merge_sort(p),
         *h2 = merge_sort(head);   // sort the two parts

    head = h1, prev = 0;
    // merge the list 'h2' into 'h1' inplace
    while(h2 != 0) {
        if(h1 != 0 && h2->val >= h1->val) {
            prev = h1;      // just iterater through 'h1' list
            h1 = h1->next;
        } else { // insert 'h2' before 'h1'
            list *t = h2->next; // save the 'next' pointer
            if(prev == 0) { // insert a new head
                h2->next = head;
                head = h2;
            } else {
                prev->next = h2;
                h2->next = h1;
            }
            prev = h2; h2 = t;
        }
    }
    return head;
}

if I understand the problem correctly, we just need to count the number of turns (left / right) while traversing a binary tree. The solution with additional storage:

std::hast_map< int, int > vsums; // the hash containing vertical sums

void compute_vsums(node *t, int n) {
    if(t == 0)
        return;
    // one turn to the left corresponds to n-1
    // turn to the right corresponds to n+1
    vsums[n] += t->val;
    compute_vsums(t->left, n-1);
    compute_vsums(t->right, n+1);
}
call compute_vsums(root, 0);

and if we do not have a parent node, then:

node *wanted; // the node whose successor we wish to find
node *find_rec(node *t, bool& found) {
    if(t == 0) {
        found = false;
        return 0;
    }
    if(t == wanted) {   // found the 'wanted' node
        found = true;   // in the traversal
        return 0;
    }
    node *x = find_recurs(t->left, found);
    if(found) {
        if(x != 0)
            return x; // the successor already found: just pass it by
        return t; // this is a successor
    }
    return find_rec(t->right, found);
}

node *inorder_succ() {
    if(wanted->right) {
        ... // proceed as in the above soln
        return t;
    }
    bool found = false; // otherwise start the search from the root
    return find_rec(root, found);
}

// infA[] - infinite array with '$' as a terminating character
bool binary_search(char *infA, char x) {

    int l = 0, r = 1;
    while(1) { // first phase: find the array bounds
        char a = infA[r - 1];
        // here we either found the valid range or hit the end of the data:
        // in any case we can reduce the search space to [l; r]
        if(a == '$' || x < a) { 
            break;
        }
        if(x == a) // found the actual val
            return true;  
        // otherwise we keep on moving the right boundary
        l = r - 1, r = r * 2;
    }
    printf("'x' can only lie between [%c; %c]\n", infA[l], infA[r]);

    // second phase: run an ordinary binary search with account for
    // the terminating symbol '$'
    while(1) {
        int mid = (l + r) / 2;
        char a = infA[mid];
        if(a == '$' || x < a) {
            r = mid;
        } else if(x > a) {
            l = mid + 1;
        } else  // gotcha !!
           return true;
        if(l == r)
            return false; // not found
    }
}

suppose `hour' is in [0..11]
and `min' is in [0..59]
we do not take seconds into account for simplicity

compute_angle(int hour, int min) {
   float ha = (float)(hour + min / 60.0f) * 360 / 12.0f; // position of hours hand
   float ma = (float)min * 360 / 60.0f; // position of minutes hand
   float a = std::abs(ha - ma);
   if(a > 180)
       a = 360 - a;
   return a; // return the angle difference
}

int max_so_far = 0;
// in each recursive call [low; up] specifies the valid range of node
// values to satisfy the BST property
int max_BST_subtree(node *t, int low, int up) {
    if(t == 0)      // found a leaf node
        return 0;
    // indicates that the BST property is broken
    if(t->val <= low || t->val >= up)
        return -1; 
    // count the number of BST nodes in subtrees
    int s_left = max_BST_subtree(t->left, low, t->val);
    int s_right = max_BST_subtree(t->right, t->val, up);
    // take either left part, right part or both
    if(s_left != -1 && s_right != -1)
        s = s_left + s_right + 1; // take both subtrees + root node
    else
        s = max(s_left, s_right); // take on of subtrees
    max_so_far = max(s, max_so_far);
    return s; // return the number of nodes found (or -1 if no BST)
}
call max_BST_subtree(root, -infty, +infty);

smth along these lines should work:

// A[n] - array containing preorder traversal of a BST
root = new node;
t = root, t->parent = 0;
t->val = A[0], split = t;

for(i = 1; i < n; i++) {
    if(A[i] < t->val) {
        add_left_child(t, A[i]);
        split = t;
        t = t->left;
        continue;
    } 
    // if split  == 0 or A[i] < split->val then just add to the right
    // child of the current node 't' otherwise find another 'split'
    if(split != 0 && A[i] > split->val) {
        t = split;
        while(t->parent != 0) {
            if(A[i] < t->parent->val)
                break;
            t = t->parent;
        }
        split = t;
    }
    add_right_child(t, A[i]);
    t = t->right;
}

@anonymous: WOW!! thanks for visualizing the schoolbook division ))

Generating digits of decimal expansion can be done,
e.g., using the following simple algorithm:

void div_periodic(int num, int denom) {

    int div = num / denom;
    int mod = num % denom;
    printf("%d.", div); // print integer part
    num = mod;
    int niters = 100;
    std::vector< int > digits;

    while(niters--) {
    num *= 10; // num is always smaller than denom
    int n_zeros = 0;
    while(num < denom) { // add the required number of zeros
        num *= 10; n_zeros++;
        digits.push_back(0);  
    }
    div = num / denom; // div is always a single digit
    mod = num % denom;

    digits.push_back(div); // add the next digit
    num = mod;
    if(num == 0)
        break;
    }
}

However, now it comes to the two main problems:

how to find where the period starts ?
how to find the length of the period ?

I think interviewers that ask such questions do not really understand the problem themselves because there is a significant amount of math behind it.

Consuling wikipedia, we find out that whenever
a denominator has factors of the form 2^a*5^b,
the resulting reciprocal is eventually periodic
but has a non-repeating sequence of digits of size max(a,b).

Now assume we know where the period starts.
The next problem is that a smaller period can be the part of larger
ones. For example, consider a decimal expansion of

1414147 / 999999999

which is 0.(001414147)

so there is no trivial way to detect it unless we know
what the maximal period of a fraction could be.

Again consulting wikipedia, we find that
the period of a reciprocal 1 / p is the order of 10 in Z/Zp,
given by Euler totient function, and is at most (p-1).

This suggests that we have to compute the first (p-1) digits
of decimal expansion of 1/p to find the period!!!

Is there another way ?

for event notification

well, honestly I did not know that STL has the algorithm 'next_permutation'.. Looking at its source code, it seems be a perfect solution to another problem, that is, generating permutations in lexicographical order

yep thanks for correction ))

I think bottom-up approach works better here, because in your algorithm you need too many recursive calls from each tree node.. look at my solution below

finally some good solution ))
I think you can do this even simpler:

given a number x = 1000111100
lo = x & -x; // locate the lowest set bit: lo = 100
lz = (x + lo) & ~x; // locate the lowest zero above lo: lz = 1000000
x += lo; // flip the 'lz' bit: x = 1001000000
x |= (lz / lo / 2); // add the rest number of ones: x = 1001000111