Representation Change in Transform and Conquer Technique

Representation Change is one of the variants of the Transfer and Conquer technique where the given problem is transformed into another domain that is more familiar or simpler to execute. In the case of representation change, the instance of a given problem is transformed into another representation without affecting the original instance.

Characteristics: 

Given below are some basic characteristics of the Representation Change technique:

• Only the representation of the instance is changed but the original instance should be retained. 
• The extraction of the result from the new representation should be more efficient than the original one.

Example:

Let us understand the representation change in a better way with the help of an example:

Consider the problem Find if there is any duplicate element in the array

Approach 1: To solve this problem one can compare each element with all other elements of the array and find if any duplicate is present in the array or not.

It can be written as follows:

• Iterate a loop from the start to the end
  • Compare each element with all the other elements.
  • If there is a match then a duplicate exists.
  • Otherwise, there is no duplicate found for the current element.
• Ultimately, after all the elements are traversed and no duplicate found in any iteration, then the array does not contain a duplicate value.

Algorithm:

Algorithm find_duplicate(A[1, 2, . . . N]):
        for i = 0 to N-1:
                temp = A[i]
                for j = i+1 to N:
                        temp1 = A[j]
                        if temp == temp1:
                                duplicate found
                        end if
                end for
        end for

Time Complexity: O(N²)
Auxiliary Space: O(1)

Approach 2 (Representation Change): The above problem is complex in the sense of comparison. It requires a lot of comparisons. This complexity can be reduced as shown below:

• Change the above array to a Red-Black Tree that will hold only unique elements (the functionality is implemented in a Set).
• If the size of the tree and the array are the same then there is no duplicate.

This is the representation change technique where the array representation is changed and the problem is solved efficiently.

The approach is as follows:

• Build an empty set (which implements the Red-Black tree).
• Insert the array elements into the set.
• If the set size and the array size are the same then there is no duplicate. Otherwise, there are duplicate elements.

Algorithm:

Algorithm find_duplicate(A[1, 2, . . . N]):
        set st[]
        for i = 0 to N:
                insert A[i] in st[]
        end for
        if sizeof(st) == N:
                no duplicate
        else:
                duplicate exists
        end if

Time Complexity: O(N * logN) which is required to insert all array elements into the set.
Auxiliary Space: O(N) 

Advantages: The advantages of the representation change method are mentioned below

• By changing the representation, the time complexity of the problem gets reduced to a large extent.
• The instance of the given problem is retained after changing its representation. 

Disadvantages: There are also a few disadvantages of the technique like:

• Constructing a new instance of the given problem is difficult and costly.