I do programming questions but many a times I come across some problem in which I think I should make an effort to reduce both time and space complexity. For example, I want to convert given coordinates (0,0 to n,n). Consider a square matrix. Now I want my program to mark the coordinates that I have already visited. For that I have to save the x,y coordinates in a pair<int,int> object. I was wondering if I could save them in a single primitive type variable. E.g. x,y ---(Function 1)----> z and z--(Function 2)--> x,y
Is this possible? Here we should get a unique value of z for every different pair of x,y and for each value of z we should get unique coordinates x,y. I want to implement these 2 functions, that do the forward and backward mapping.
If you are dealing with integers then $$z=x+(n+1)y$$ would work in one direction while rounding down with the floor function (or integer division) $$y = \lfloor z/(n+1)\rfloor \text{ and } x=z-(n+1)\lfloor z/(n+1)\rfloor$$ would work in the other. Since $0 \le x \le n$ and $0 \le y \le n$ you have $0 \le z \le n^2+2n$, and this is in effect a bijection.