Illustration Change in Switch and Conquer Method

Illustration Change is without doubt one of the variants of the Switch and Conquer approach the place the given drawback is reworked into one other area that’s extra acquainted or easier to execute. Within the case of illustration change, the occasion of a given drawback is reworked into one other illustration with out affecting the unique occasion.

Traits: 

Given beneath are some fundamental traits of the Illustration Change approach:

• Solely the illustration of the occasion is modified however the unique occasion needs to be retained. 
• The extraction of the outcome from the brand new illustration needs to be extra environment friendly than the unique one.

Instance:

Allow us to perceive the illustration change in a greater manner with the assistance of an instance:

Take into account the issue Discover if there’s any duplicate aspect within the array

Method 1: To unravel this drawback one can examine every aspect with all different parts of the array and discover if any duplicate is current within the array or not.

It may be written as follows:

• Iterate a loop from the begin to the tip
  • Evaluate every aspect with all the opposite parts.
  • If there’s a match then a reproduction exists.
  • In any other case, there is no such thing as a duplicate discovered for the present aspect.
• In the end, in spite of everything the weather are traversed and no duplicate present in any iteration, then the array doesn’t include a reproduction worth.

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 discovered
                        finish if
                finish for
        finish for

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

Method 2 (Illustration Change): The above drawback is advanced within the sense of comparability. It requires a whole lot of comparisons. This complexity might be lowered as proven beneath:

• Change the above array to a Purple-Black Tree that can maintain solely distinctive parts (the performance is applied in a Set).
• If the scale of the tree and the array are the identical then there is no such thing as a duplicate.

That is the reepresentation change approach the place the array illustration is modified and the issue is solved effectively.

The strategy is as follows:

• Construct an empty set (which implements the Purple-Black tree).
• Insert the array parts into the set.
• If the set dimension and the array dimension are the identical then there is no such thing as a duplicate. In any other case, there are duplicate parts.

Algorithm:

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

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

Benefits: Some great benefits of the illustration change technique are talked about beneath

• By altering the illustration, the time complexity of the issue will get lowered to a big extent.
• The occasion of the given drawback is retained after altering its illustration. 

Disadvantages: There are additionally a couple of disadvantages of the approach like:

• Developing a brand new occasion of the given drawback is troublesome and dear.