Reasons for preferring C++ over Java in Coding competitions

Some time back, a question was asked on Codechef that "Why majority of programmers use C++ and not Java for submitting solutions". I posted an answer which was well received, here is my blog version of the answer.

Lets first understand the question-

It is a known fact that C++, C and Java dominate the domain of systems programming. And they are quite close in terms of popularity, in terms of usage. But the scene on programming competition sites like TopCoder, Codechef, SPOJ etc. is rather lopsided. Majority of programmers use C or C++. In fact for a typical problem C/C++ submissions are as high as 85%. Java getting second position at some ~10%, and rest is C#, python, pascal etc. You can research on your own, by going through All Submissions of Codechef.

So here are my reasons in point form-

1. Main reason is definitely the speed of execution. C or C++ is far ahead of Java in this. I won't elaborate as to why C++ is faster here.
2. Also in C++ you can get away with procedural style of programming, but Java forces you to write OO program. Which is unnecessary burden for programming on codechef.
3. No pointers? No pass by reference? Seriously this is a put off.
4. Top programmers are wicked! And C++ allows you to do wicked things. For example macros. Can you do this in Java?
5. C++ has STL, which is awesome. So argument "Java definitely has more inbuilt functionality than c++" is invalid. Whenever I see C++ beating C, I immediately understand that it has got to do with STL.
6. Taste. Yes a language is supposed to be tasty. Java syntax is rather mundane. C++ packs a lot of spicy operators.
7. Generics are not as powerful as templates. I don't know whether people use either of them on codechef, but it is a fact. With C++ templates, you can do a lot of work at compile time.
8. Also it is possible that C++ is taught before Java (as in my case). Which I think is again for a good reason.

I have omitted many points of difference between C++ and Java, because they are not relevant in Codechef programs are quite small. But 80% of time, Java losses. Which is yet another reason for programming in C++ on Codechef.
Note 1 - I am not suggesting that Java programmers should become C++ programmer. Code in the language, you are comfortable in. And both languages are good enough for all sorts of programming. This answer is merely an answer to the question.
Note 2 - Feel free to correct me, if I said anything wrong.

In addition, there is a saying "Rich gets richer, poor gets poorer", which I think is valid in this context. The problem setters and testers most of the time, test the solutions in C or C++. So the Time Limit for slower languages like Python, or the esoteric ones like Prolog, maybe unjust (even after giving them 2x to 6x time compared to C).

This post is not supposed to bash Java language, its just my true observations regarding C++ and Java.

Greatest Common Divisor (GCD) C++ Program

One of the most useful math function is Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF). It takes 2 (or more) integers (positive or negative, but not zero) and returns the largest positive integer which divides the input integers without leaving remainder.

Examples-
* GCD(2, 4) = 2 because 2 divides both 2 and 4, and there is no other integer bigger than 2 which can do this.
* GCD(16, 24) = 8
* GCD(5, 6) = 1
* GCD(-2, 6) = 2

There are several ways to compute GCD as given on Wikipedia page, but we will use Euclid's algorithm, which is well suited for programming.

Note - Take care that the arguments are positive integers only. You can call GCD(abs(a), abs(b)) to ensure the negative integers are converted to positive.
The recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

The non-recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Let's trace GCD(18, 88) to see how code works for recursive version-

GCD(18, 88) => GCD(88, 18) => GCD(18, 16) => GCD(16, 2) => GCD(2, 0) => 2

Reverse a linked list in group of k

This is one of a candidate interview question. I don't see any practical application of this-

Given a linked list, reverse the list in groups of size k. 

I am sure it is not clear to you, so here is a example-
Input -    1=>2=>3=>4=>5=>6=>7=>8
Output -  3=>2=>1=>6=>5=>4=>8=>7

Try solving it yourself before going through the code.

#include <stdio.h>
#include <stdlib.h>

typedef struct node 
{
 int v;
 struct node *next;
} node;

node * revk(node *head, int k)
{
 int i = 1;
 node *p, *b, *s1, *s2, *t;
 p = head;
 b = NULL;
 s1 = NULL;
 s2 = head;

 while (p)
 {
  t = p;
  p = p->next;
  if (t)
   t->next = b;
  b = t;

  if (i == k)
  {
   if (s1)
    s1->next = b;
   else
    head = b;
   s1 = s2;
   s2 = p;
   i = 0;
  }
  i++;
 }
 s1->next = b;
 s2->next = NULL;
 return head;
}

void print(node *head)
{
 node *p = head;
 while (p)
 {
  printf("%d -> ", p->v);
  p = p->next;
 }
 printf("$\n");
}

void insert(node **t, int v)
{
 node *p = malloc(sizeof(node));
 p->v = v;
 p->next = NULL;
 (*t)->next = p;
 *t = p;
}

int main(int argc, char *argv[])
{
 node *head, *tail = NULL;
 head = malloc(sizeof(node));
 head->next = NULL;
 head->v = 1;
 tail = head;
 insert(&tail, 2); 
 insert(&tail, 3); 
 insert(&tail, 4); 
 insert(&tail, 5); 
 insert(&tail, 6); 
 insert(&tail, 7); 
 insert(&tail, 8);

 print(head);

 head = revk(head, 3);

 print(head);

 tail = head;

 while (tail)
 {
  head = tail;
  tail = tail->next;
  free(head);
 }

 printf("\n");
 return 0;
}

C Program : Rank of a word

Rank of a word is the position of the word when all the permutations of the letters in the word are listed in dictionary order. So for example "cat" is the word, then, various permutations in dictionary order are-

1. act
2. atc
3. cat
4. cta
5. tac
6. tca

Hence the rank of "cat" is 3.
Here is the logic in short-

Sort the word, find number of permutations that can be formed with letters which come before i^th letter in original word.

So for i = 0, i^th letter is 'c' and the sorted word is "act", so we need to find all permutations starting with 'a' and so on.

Below is the program that takes care of duplicates as well.

#include <stdio.h>
#include <string.h>

long fact(int n)
{
 long f = 1;
 while (n > 0)
 {
  f *= n;
  n--;
 }
 return f;
}

int find_rank(char s[], int len)
{
 long rank = 1;
 int i, j, k, l, fr[26], f; //fr is frequency
 char sorted[100], cur, t, pre;

 for (i = 0; i < len -1 ; ++i)
 {
  cur = s[i];
  strcpy(sorted, s + i);
  l = len - i;
  memset(fr, 0, sizeof(fr));
  fr[sorted[0] - 'a']++;
  for (j = 1; j < l; ++j)
  {
   t = sorted[j];
   fr[t-'a']++;
   for (k = j-1; k >=0 && sorted[k] > t; --k)
    sorted[k+1] = sorted[k];
   sorted[k+1] = t;
  }
  pre = 1;
  for (k = 0; sorted[k] != cur ;++k)
  {
   if (sorted[k] == pre)
    continue;
   pre = sorted[k];

   f = fact(l - 1);
   fr[pre - 'a']--;
   for (j = 0; j < 26; ++j)
    if (fr[j])
     f /= fact(fr[j]);
   rank += f;
   fr[pre - 'a']++;
  }
 }
 return rank;
}

int main()
{
 char s[100];
 
 scanf("%s", s);
 printf("%d", find_rank(s, strlen(s)));
 return 0;
}