Fast integer input function in C

There can be few problems on online judges with large input data. Using traditional funcitons like scanf() for taking input would not work in such cases. So a function for taking faster inputs does effect final result.

Here is a function that reduces execution time in taking inputs of integeral numbers.

int get_num()
{
	int num = 0;
	char c = getchar_unlocked();
	while(!(c>='0' && c<='9'))
		c = getchar_unlocked();
	while(c>='0' && c<='9')
	{
		num = (num<<3) + (num<<1) + c -'0';
		c = getchar_unlocked();
	}
	return num;
}

How it works?

getchar_unlocked() is the function in C that takes inputs of character. It is much much faster in taking an input compared to scanf().

Coming to the functioning of function, c is a character variable and num is integer variable in which input number will be taken. Initially taking ‘c’ and checking if it lies in values between ‘0’ and ‘9’(It checks in ASCII order). Once you find the value of ‘c’ in the range, it gets into second while loop. Here, num value is changing the every time. It is indeed multiplied by 10, when everytime the while loop is repeated. Finally while loop breaks when c is some other character other than integral digit(in general will be a space or ‘\n’).

Atlast it returns the given input number. But this function is only for +ve integers. We can make a function for taking numbers including -ve numbers also.

It goes this way..

int get_num()
{
	int num = 0;
	char c = getchar_unlocked();
	int flag = 0;
	while(!((c>='0' & c<='9') || c == '-'))
		c=getchar_unlocked();
	if(c == '-')
	{
		flag = 1;
		c=getchar_unlocked();
	}
	while(c>='0' && c<='9')
	{
		num = (num<<1)+(num<<3)+c-'0';
		c=getchar_unlocked();
	}
	if(flag==0)
		return num;
	else
		return -1*num;
}

There is another function using fread() which takes much faster input.. you can read about that here.. FAST_I/O

Advertisements

Methods to check if a number is prime or not

One of the most common problem a competetive programmer solves is regarding prime numbers. A beginner, in general starts solving such problem by following the definition of prime numbers i.e. a prime number is that which is not divisible by any number other than 1 and itself.
So, following this, the pseudocode will be in this way..

n <- input
i <- 2
while i < n
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i = n
    "PRIME"

It has an O(n) complexity. But the competetive programming never would ask a question that allows one to get their code accepted in time limit with such an approach. They would demand a much better approach.

A better approach would let us know the concept that ‘a number is not prime if it has a factor that is less than or equal to square root of n’. With this pseudocode can be..

while i*i <= n   //(loop will be iterated till 'i' is atmost square root of n)
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i*i > n
    "PRIME"

This code has a complexity of O(sqrt(n)).

Now just think you need to check a if number of order 10^8 is prime or not, previous approach would take 10^8 iterations in solving. Whereas later takes just around 10^4 iterations in solving your problem.