Nuts and Bolts Problem OR Lock and Key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {

    public static void matchPairs(char[] nuts, char[] bolts) {
        for (int i = 0; i < nuts.length; i++) {
            char nut = nuts[i];
            for (int j = 0; j < bolts.length; j++) {
                if (nut == bolts[j]) {
                    swap(bolts, i, j);
                    break;
                }
            }
        }
        System.out.println("Matched nuts and bolts are:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }

    // Swap method to exchange elements in the array
    public static void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};
        
        matchPairs(nuts, bolts);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def match_pairs(nuts, bolts):
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]  # Swap elements in the array

    for i in range(len(nuts)):
        nut = nuts[i]
        for j in range(len(bolts)):
            if nut == bolts[j]:
                swap(bolts, i, j)
                break

    print("Matched nuts and bolts are:")
    print("Nuts:  ", nuts)
    print("Bolts: ", bolts)

# Example usage
if __name__ == "__main__":
    nuts = ['@', '#', '$', '%', '^', '&']
    bolts = ['$', '%', '&', '^', '@', '#']
    
    match_pairs(nuts, bolts)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Solution {

    public static void matchPairs(char[] nuts, char[] bolts) {
        // Create a HashMap for nuts, with nut as key and its position as value
        HashMap<Character, Integer> nutMap = new HashMap<>();
        for (int i = 0; i < nuts.length; i++) {
            nutMap.put(nuts[i], i);
        }

        // For each bolt, check for the nut in the HashMap
        for (int i = 0; i < bolts.length; i++) {
            char bolt = bolts[i];
            if (nutMap.containsKey(bolt)) {
                nuts[i] = bolt;  // Place the matching nut in the correct position
            } else {
                System.out.println("For bolt " + bolt + " no matching nut is present.");
                return;
            }
        }

        System.out.println("(Hash Map) Matched nuts and bolts are:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};
        
        matchPairs(nuts, bolts);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def match_pairs(nuts: List[str], bolts: List[str]) -> None:
    # Create a dictionary for nuts, with nut as key and its position as value
    nut_map = {nut: i for i, nut in enumerate(nuts)}

    # For each bolt, check for the corresponding nut in the dictionary
    for i in range(len(bolts)):
        bolt = bolts[i]
        if bolt in nut_map:
            nuts[i] = bolt  # Place the matching nut in the correct position
        else:
            print(f"For bolt {bolt} no matching nut is present.")
            return

    print("(Hash Map) Matched nuts and bolts are:")
    print("Nuts:  ", nuts)
    print("Bolts: ", bolts)

    # Example usage
if __name__ == "__main__":
    nuts = ['@', '#', '$', '%', '^', '&']
    bolts = ['$', '%', '&', '^', '@', '#']

    match_pairs(nuts, bolts)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

public class Solution {

    private static void matchPairs(char[] nuts, char[] bolts, int low, int high) {
        if (low < high) {
            // Choose the last element of nuts as pivot to partition bolts
            int pivotIndex = partition(bolts, low, high, nuts[high]);
            // Partition nuts with the matched bolt
            partition(nuts, low, high, bolts[pivotIndex]);

            // Recursively apply the partitioning to the remaining elements
            matchPairs(nuts, bolts, low, pivotIndex - 1);
            matchPairs(nuts, bolts, pivotIndex + 1, high);
        }
    }

    private static int partition(char[] array, int low, int high, char pivot) {
        int i = low;

        // Partition the array based on the pivot
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                swap(array, i, j);
                i++;
            } else if (array[j] == pivot) {
                swap(array, j, high);
                j--;
            }
        }
        swap(array, i, high); // Restore the pivot element to its position
        return i;
    }

    private static void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        char[] nuts = {'@', '#', '$', '%', '^', '&'};
        char[] bolts = {'$', '%', '&', '^', '@', '#'};

        matchPairs(nuts, bolts, 0, nuts.length - 1);

        System.out.println("Matched nuts and bolts:");
        System.out.println("Nuts:  " + Arrays.toString(nuts));
        System.out.println("Bolts: " + Arrays.toString(bolts));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
    def match_pairs(self, nuts: List[str], bolts: List[str]) -> None:
        def partition(arr: List[str], low: int, high: int, pivot: str) -> int:
            i = low
            for j in range(low, high):
                if arr[j] < pivot:
                    arr[i], arr[j] = arr[j], arr[i]
                    i += 1
                elif arr[j] == pivot:
                    arr[j], arr[high] = arr[high], arr[j]
                    j -= 1
            arr[i], arr[high] = arr[high], arr[i]
            return i

        def match_pairs_util(nuts: List[str], bolts: List[str], low: int, high: int) -> None:
            if low < high:
                pivot_index = partition(bolts, low, high, nuts[high])
                partition(nuts, low, high, bolts[pivot_index])
                match_pairs_util(nuts, bolts, low, pivot_index - 1)
                match_pairs_util(nuts, bolts, pivot_index + 1, high)
        
        match_pairs_util(nuts, bolts, 0, len(nuts) - 1)

# Example usage
sol = Solution()
nuts = ['@', '#', '$', '%', '^', '&']
bolts = ['$', '%', '&', '^', '@', '#']
sol.match_pairs(nuts, bolts)

print("Matched nuts and bolts:")
print("Nuts:  ", nuts)
print("Bolts: ", bolts)