A trick for Rough work

I use a lot of my notebooks and registers and write a lot of rough notes at the back pages while I am thinking or practicing.

The one problem I was faced was with how to jot down longer notes, like programs, derivations or simply anything that ran much longer than a page, because then I'd be forced to write stuff in reverse order (E.g - begin on page 320, then goto page 319 when I run out of space, etc).

So a simple way to write rough notes would be to start upside down.

Instead of writing in the usual fashion, rotate your register/notebook by 180^o.

This has the advantage that you can continue to the next page, which is actually the previous page on your notebook, but still maintain readability.

Double Factorial

So today while reading wiki for graph algorithms, I came across this term n!! called double factorial. Naturally, I was petrified. A factorial time complexity is scary enough, how horrible would double factorial be? In my mind I was assuming all sorts of irrational expressions such as:

n!! = (n-1)!!(n-1)!!
     = ((n-2)!! (n-2)!!)( (n-2)!! (n-2)!!)
     = ... [You get it, right?]

But as it turns out, double factorials are not so bad after all. Actually:

n!! = n*(n-2)* (n-4)*(n-6)*...

With terminal conditions 0!! = 1!! = 1.

So, a double factorial is actually has similar complexity to sqrt(n!).

Great!

  
                  

LeetCode - Q214 - Shortest Palindrome

This question, despite being solvable by a simple O(n^2) algorithm, almost took 2 hours of my life.

Simply because I was trying to get sub-palindromes, when instead, I should have checked for longest prefix of original string matching the suffix of its reverse.

E.g.           s = "abcda"

              reverse of s = rev = "adcba"

         longest suffix of rev matching s = "a"

              Answer = "adcbabcda"
           


class Solution {
public:
    string shortestPalindrome(string s) {
        string rev = s;
        int n = s.size();
        reverse(rev.begin(),rev.end());
        for(int i=n;i>0;i--)
        {
            if(!strncmp(s.substr(0,i).c_str(),rev.substr(n-i,i).c_str(),i))
                return rev.substr(0,n-i)+s;
        }
        return rev+s;
    }
};

Reinventing the wheel

So, I felt like I needed some coding exercise, and also was feeling a little interested in doing that in JS. Since I am not big on ideas, I went and implemented my version of Tic-Tac-Toe. The front end isn't all that, but at least it works (and looks quite nice too, I think).

Round-off in C (C++ too)

I think the best way to round off decimals in C for output would be to simply adjust the accuracy in the printf function. The following code demonstrates that-

#include<stdio.h>

main()

{

float a = 3.56449;

printf("\n%.2f",a);

printf("\n%.3f",a);

printf("\n%.4f",a);

printf("\n%.1f",a);

printf("\n%.0f",a);

}

One thing though, you don't get rolling round-offs, i.e, 3.56449 becomes 3.564 and not 3.565.

The recursive main()

I didn't think that way, but it turns out that main() function can be used recursively in C. So, for instance, the given code is completely valid and runs on any GCC compiler.

#include<stdio.h>

int a = 10;

main()

{

while(a)

{   

    a--;

    printf("%d\n",a);

    main();  // Here it is

}

}

I don't know how useful this maybe, but it can be handy for some real nice MCQs related to code obfuscation.