Swapping without a temporary variable : Take Care

Originally posted here.

This must be the easiest program, after “Hello World”, we have ever written.

Even we don’t need a compiler to test the result, right?
We can submit it blindly if we get such question in our Competitive Programming world, won’t we?

Nevertheless, this might be the most frequently asked, most famous question in interviews, oh I forgot, with a additional condition of **Don’t use any temporary variable**! Did your interviewer not ask this?

Today I have few methods for doing the same.

This is going to be a quite short and quick post, but yet I will give you an important/useful note at the end. This is not which I have planned, but it struck my mind and I thought it’s worth sharing.

So, Lets start with our different solutions:-

For all the solutions, Consider `a` & `b` are our variables.
`a = 5` and `b = 10`.

1. Using the temporary variable

void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}

2. Without using temporary variable, with addition-subtraction

void swap(int &a, int &b)
{
a = a + b;
b = a – b;
a = a – b;
}

3. Without using temporary variable, with multiplication-division

void swap(int &a, int &b)
{
a = a * b;
b = a / b;
a = a / b;
}

4. Without using temporary variable, with XOR operation

void swap(int &a, int &b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}

5. One liner with addition-subtraction

void swap(int &a, int &b)
{
a = a + b – (b = a);
}

6. One liner with multiplication-division

void swap(int &a, int &b)
{
a = a * b / (b = a);
}

7. One liner with XOR

void swap(int &a, int &b)
{
a ^= b ^= a ^= b;
}

8. Using a temporary variable, with a macro:

#define swap(type,a,b) type temp;temp=a;a=b;b=temp;

Cool enough?

Did you not like this?

Though These one liners or without-temporary-variable thing looks cool, simple and tricky, fancy; these have their own problems associated with them.

Lets have look at problems associated with each method.

Methods 2, 3, 5, 6:

Will these methods give you answer if values of a and b are huge?
say MAX_INT is the maximum value of integer that can be accommodated in a and b.
The moment we add a & b, or multiply them, They are going to overflow, they don’t fit in our 32 bit size.
We will get WA (wrong answer).

Methods 3, 6:

Will these method work if any of a or b is 0?
We are going to get Divide by zero error.

Methods 4, 7:

These methods appear to be clean, because they don’t fail for any test-case, but again since (as in method 7) value of variable is modified twice within the same sequence point, it is undefined behavior declared by ANSI C.
(Those, who are curious about sequence points, I will cover that topic in some other note).

Method 8:

We call that macro from our code as :

swap(int, a, b)

Right?

That macro get substituted in our code as:

int temp;
temp=temp;
temp=b;
b=temp;

To be honest, don’t we use some variable as `temp`?

Again, the name conflict.

To summaries this, I just want to tell you, avoid doing this in any of the above fancy ways (unless asked in interviews :p ). Stick to the basics i.e. Method 1. It is easy to write, easy to maintain too.

 Oh, I have one more way :p

 A gift for Python programmers:

a, b = b, a

I hope you liked this post.

If you really like this, Let me know! 🙂

Gaussian Elimination Technique

Gaussian Elimination is a technique traditionally used to solve linear equations, finding determinant, rank of matrix, inverse of matrix. If you don’t remember it, have look at this video.

Today we will be applying the same technique to solve a problem. Wasting no time, lets proceed.

The problem is to find the subset of no.s from given set so as to get maximum value if all no.s in subset are EX-ORed.
This problem is known with id XMAX on SPOJ.
The variant of this problem was there on CodeChef with name XOR with Subset.

Here, I will try to give you a step by step method to solve the problem:

  1. The idea here is to choose a no. which has MSB with maximum value. With a little thinking, we will get the max(array) will have this feature. Say, maximum of array is a k-bit no. and that no. is M. Now, there can be multiple no.s which are k-bit no.s and have the same highest-value bit as ‘1’. So in that case we will EX-OR each of them with the M and put them again input array (ideally, we can choose any one of those k-bit no.s as M and put others in array after ex-oring with it). At the same time we will keep the no. M in some other array say x[].
  2. We will keep doing step 1 until we get 0 as maximum in the array i.e. this loop will run for iterations = no. of bit the maximum of array is.
  3. Now will have a x[] array which will be of size = no. of bit the maximum of array is
  4. Now we will initialize the answer variable to given 0 and loop for each value in array x[], if value of answer variable is going to increase with the inclusion of ith element, we will update the answer variable with the new value as answer ^ x[i], else we will keep it as is.
  5. Finally returning the value of answer solves our problem.

This solves our problem and we can get it AC on SPOJ.
Now the change in CodeChef problem is the compulsion of including the given no. and then finding the subset which gives the maximum value.
Nothing to worry about.
Simply we need to initialize answer variable to the given no. instead of a 0 (as we do in step 4) and, solution gets AC on CodeChef too.

The main logic here is to try making every bit of answer to be ‘1’. Our x[] will have elements having different set bits position so when we ex-or them with answer variable, answer variable will have more no. of set bits.

I hope I am successful in giving you the procedure. Have look at the code for more clarification.

 

If you like this post, click the LIKE button right below.

To stay updated with this blog, just click on the FOLLOW button on right-bottom corner and get every new post delivered to your Inbox.

Thank you.

Small Discussion about problems in PICT Code Sprint 2 on HackerEarth

1501121_579085572225985_2088954303914017907_o

Contest Link: PICT CS2

It was a good contest. 5 not so difficult, but at the same time not so easy to get full score kind of problems were there. After successfully completing the contest, lets have a quick small discussion on all 5 problems.

Xenny and Questions

Quick Explanation of problem:
Xenny is in exam and has n questions with different marks in paper. He needs 1 unit time to solve a questions and has unit time to finish the test. He wants to score maximum marks and you are going to find this score – maximum score that he can get.

Solution:
Since Xenny needs same amount of time for each question, this is not a knapsack problem. There are n questions and we want to choose k so as to have maximum marks, we can do this by greedy approach i.e. choose k questions with maximum marks. Hence simple sorting solves the problem.
Wait, there is a catch. The time limit.
Time limit was such that O(nlogn) solution will not get full score. Hence sort() in STL or qsort() didn’t solve the problem completely. Here you need a faster sorting method. And the method is Counting Sort which sorts in O(n). Its a simple method for sorting which stores the elements in different way. It is a kind of hashing. It works by counting the number of elements having distinct key values.
Also you can have look for more explanation of this technique here.

Xenny and Composite Number

Quick Explanation of problem:
Given a number n,  you have to find the composite number greater than that number.

Solution:
This is again a simple problem. We will assume that we have list of prime number and checking the number to be prime can be done in O(1). We can see, if the n is prime, n+1 will definitely be composite (except for n=2).
If n is not prime, then we are not sure about composite-ness (or prime-ness) of n+1, hence in that case we will check n+1 if it is prime. If it is prime, then n+2 has to be composite. Else n+1 was our answer. The only cases remain un-discussed are n = 0, 1 or 2 which we can easily hard code.
Now finding all primes in given range! Catch!! Time limit!!!.
Since the range of n was till 10^5, the O(n^2) solution would not have worked because at the end, we want an array of boolean-s in which ith index will tell if is prime number or not. The best method for this situation was Sieve of Eratosthenes. This method is the method we learnt in third standard.
Also you can have look for more explanation of this technique here.

Xenny and Prime Factorization

Quick Explanation of problem:
Given a and b,  you have to find the prime factors of a raised to b, a^b.

Solution:
The first step is the most important here. If you literally start with finding a^b and then its prime factorization, you are taking wrong step and your solution is not going to work since a and b are quite large numbers it will easily overflow the range of long long int too. If you give a little thought before solving, you will get that you just need to find factorization of and then just multiply the powers of all prime numbers with b and output them.
Remember the rule learnt in school: (a^m)^n = a^(m*n).
The task of finding prime factorization of is quite easy.

Xenny and Girlfriend

Quick Explanation of problem:
Given a graph, check if you can visit all edges exactly once.

Solution:
Given a thought, you will know that this task is only possible if we have # of entrance = # of exit to any node (except for start node and end node) i.e. in-degree should be equal to out-degree. It is little harder for me to explain this, so you have to check this yourself for some examples (but it is true, really). Since the given graph was un-directed, our task is even simpler. Just calculate degrees of all junctions  if they are even or odd and check if # of junctions with odd-degree are 0 or 2. If # of junctions with odd degree = 0 or 2, possible; else Not-possible.
This concept is Eulerian Path. Read this for detail explanation.

Xenny and Matching Pairs

Quick Explanation of problem:
Find the maximum number of pairs you can match without crossing the other pairs.

Solution:
Again, in this problem too, you have to think hard first and then solve.This is a variant of standard problem called Longest Increasing Sub-sequence. I believe, you can map this problem with Longest Increasing Sub-sequence after reading this.

Solving the Longest Increasing Sub-sequence
The dynamic programming solution will get partial points because it has a time complexity of O(n^2). But the same problem also has a O(nlogn) solution.

We hope you would have enjoyed this contest. The motto behind these contests is always Learning and we hope you got something to learn. Any feedback, suggestions about the contest or this blog are always welcome.

If you like this post, hit the LIKE button right below.

To stay updated with this blog, just click on the FOLLOW button on right-bottom corner and get every new post delivered to your Inbox.

Thank you.

Modular Arithmetic

Topics:
1. Introduction
2. Addition-Subtraction
3. Multiplication
4. Division / Modular Inverse

1. Introduction
In most of the problems on online competitive programming platforms, we are asked to return the answer modulo m which is usually a huge prime number. In this blog-post, I am going to cover basics of the Modular Arithmatic operations which are sufficient to solve those problems.

2. Addition-Subtraction
The Modular Addition is a quite simple operation. This is as follows:
(a+b)%m = ((a%m) + (b%m))%m
Or
(a+b)%m = ((a%m)+b)%m.</p>

Now what about (a-b)%m?
Can we write (a-b) as (a+(-b))?
Yes, we can. Now we can apply the same addition operation stated above. Simple enough!
Wait, there is a catch here!! How are we going to find modulo m value of a negative number?
Remember that, (-b%m) != -(b%m).
Well, your computer can do it directly, but we should know how to do it manually as well.
The solution is to add a multiple of m in b so that we will have a positive answer i.e. if we get
k*m + (-b) > 0, then (-b%m) ~= (k*m + (-b))%m.

Oh, did you just ask why does this work?
Again apply the modular addition operation on R.H.S. and we know (k*m)%m => 0.

Again the problem is to find k?
This actually should not be the problem. Just to give you the formula,
k = ceil(b/m)
The proof of this is kept up to you.

3. Multiplication
Modular multiplication is again a cakewalk. Just replace addition operator by multiplication.
(a*b)%m = ((a%m) * (b%m))%m
Or
(a*b)%m = ((a%m)*b)%m.

4. Division / Modular Inverse
Now, lets move on to modular division operation. Be a little more attentive here, because though modular division is also a simple operation; but it is not as straight forward as the others.
We want to find the answer of (a/b)%m, right?
Can we write a/b as a*(1/b) %m?
Yes. And now apply modular multiplication.
Hence, (a/b)%m = ((a%m)*(1/b)%m)%m.
Easy.

But how will we find ((1/b)%m) i.e. (inverse of b (mod m))?

Again, ((1/b)%m) != 1/(b%m)! So lets check how to find modular inverse first and then construct a formula for modular division too.

Calculating Modular Inverse:
If a*a^-1 = 1, then we call a^-1 be inverse of a.
Now modular inverse is a*a^-1 = 1 (mod m).
How to find a^-1?

The Fermat’s theorem says that:
If p is prime and GCD(a, p) = 1, then a^(p-1) = 1 mod p.

We will write a^(p-1) as (a*a^(p-2)).
Therefore,
a*a^(p-2) = 1 (mod p)
comparing with,
a*a^-1 = 1 (mod p).
We get,
a^-1 = a^(p-2) (mod p).
This is the way we find modular inverse.
Now, substituting it in our modular division equation,
(a/b)%m = ((a%m)*(b^(m-2)%m))%m.

This is all about modular arithmetic.


Now the only last question that remains unanswered is about finding a^(p-2)%p since p is usually a huge prime no. We will see that too.

Finding (x^y) % m
This will not be efficient if we go linearly. The complexity will be O(y). But since y can be huge, we should be able to do in less complexity.
Yes, we have solution for this in O(log(y)) complexity.
Here is the solution for it:

###Exponentiation(x**y) in O(log n).
def power(x, y):
if (y==0):
return 1
temp = power(x, int(y/2))
if (y%2 == 0):
return (((temp%m)*temp)%m)
else:
return ((((x*temp)%m)*temp)%m)

The solution is self-explanatory.

You can search for exponentiation and Fermat’s theorem for more details. Also, you can visit this for more properties and proofs of Modular arithmetic.

If you like this post, hit the LIKE button right below.

To stay updated with this blog, just click on the FOLLOW button on right-bottom corner and get every new post delivered to your Inbox.

Thank you.