Nuts & Bolts Problem (Lock & Key problem)

Objec­tive:  Given ‘n’ Nuts and ‘n’ Bolts of different sizes. There is one-to-one mapping between nuts and bolts. Write an algorithm to find all matches between nuts and bolts

Note: This problem can also be framed as- Given ‘n’ keys and ‘n’ locks. There is one-to-one mapping between keys and locks, means each lock has a specific key and can be unlocked using that key only. Write an algorithm to find all matches between keys and locks.

You are allowed to compare only nuts with bolts (or keys with locks), nuts with nuts or bolts with bolts comparisons are not allowed.

Example:

[] nuts = {'

Approach:

Brute Force –

Compare each nut (or key) will all the bolts (or locks) till we do not find the match.

Time Complexity: O(n2)

Code: Run Code

    

      

        

  

    
  


      

      

        

        
import java.util.Arrays;
      
      

        

        


      
      

        

        
public class NutsAndBoltsBruteForce {
      
      

        

        


      
      

        

        
    public static void match(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(Arrays.toString(nuts));
      
      

        

        
        System.out.println(Arrays.toString(bolts));
      
      

        

        
    }
      
      

        

        


      
      

        

        
    public static void swap(char [] bolts, int i, int j){
      
      

        

        
        char temp = bolts[i];
      
      

        

        
        bolts[i] = bolts[j];
      
      

        

        
        bolts[j] = temp;
      
      

        

        
    }
      
      

        

        
    
      
      

        

        
    public static void main(String[] args) {
      
      

        

        
        char [] nuts = {'$', '%', '&', 'x', '@'};
      
      

        

        
        char [] bolts = {'%', '@', 'x', '$', '&'};
      
      

        

        
        match(nuts,bolts);
      
      

        

        
    }
      
      

        

        
}
      



  

  


      
      

        view raw
        NutsAndBoltsBruteForce.java
        hosted with ❤ by GitHub
      
    


Run Code
Use Hash Map:



 	
Insert all the nuts as key and its position as value into Hash Map.


 	
Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.




Code: Run Code


    

      

        

  

    
  


      

      

        

        
import java.util.Arrays;
      
      

        

        
import java.util.HashMap;
      
      

        

        


      
      

        

        
public class NutsAndBoltsHashMap {
      
      

        

        


      
      

        

        
    public static void match(char[] nuts, char[] bolts) {
      
      

        

        
        //Create a HashMap for nuts, nut as key and its position as value
      
      

        

        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
      
      

        

        
        for (int i = 0; i < nuts.length; i++) {
      
      

        

        
            map.put(nuts[i], i);
      
      

        

        
        }
      
      

        

        


      
      

        

        
        //for each bolt , check for the nut in map
      
      

        

        
        for (int i = 0; i < bolts.length; i++) {
      
      

        

        
            char bolt = bolts[i];
      
      

        

        
            if (map.containsKey(bolt)) {
      
      

        

        
                nuts[i] = bolts[i];
      
      

        

        
            } else {
      
      

        

        
                System.out.println("for bolt " + bolt + " no nut is present.");
      
      

        

        
                return;
      
      

        

        
            }
      
      

        

        
        }
      
      

        

        
        System.out.println("(Hash Map) Matched nuts and bolts are: ");
      
      

        

        
        System.out.println(Arrays.toString(nuts));
      
      

        

        
        System.out.println(Arrays.toString(bolts));
      
      

        

        
    }
      
      

        

        


      
      

        

        
    public static void main(String[] args) {
      
      

        

        
        char[] nuts = {'$', '%', '&', 'x', '@'};
      
      

        

        
        char[] bolts = {'%', '@', 'x', '$', '&'};
      
      

        

        
        match(nuts, bolts);
      
      

        

        
    }
      
      

        

        
}
      



  

  


      
      

        view raw
        NutsAndBoltsHashMap.java
        hosted with ❤ by GitHub
      
    


 Run Code
Output:

(Hash Map) Matched nuts and bolts are:
[%, @, x, $, &]
[%, @, x, $, &]

Reference - http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/
, '%', '&', '*', 'x'}

[] bolts = {'%', 'x', '*', 'Approach:
Brute Force –
Compare each nut (or key) will all the bolts (or locks) till we do not find the match.
Time Complexity: O(n2)
Code: Run Code










import java.util.Arrays;








public class NutsAndBoltsBruteForce {








    public static void match(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(Arrays.toString(nuts));



        System.out.println(Arrays.toString(bolts));



    }








    public static void swap(char [] bolts, int i, int j){



        char temp = bolts[i];



        bolts[i] = bolts[j];



        bolts[j] = temp;



    }



    



    public static void main(String[] args) {



        char [] nuts = {'$', '%', '&', 'x', '@'};



        char [] bolts = {'%', '@', 'x', '$', '&'};



        match(nuts,bolts);



    }



}





        view raw

        NutsAndBoltsBruteForce.java

        hosted with ❤ by GitHub
      


Run Code

Use Hash Map:

Insert all the nuts as key and its position as value into Hash Map.
Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.

Code: Run Code










import java.util.Arrays;



import java.util.HashMap;








public class NutsAndBoltsHashMap {








    public static void match(char[] nuts, char[] bolts) {



        //Create a HashMap for nuts, nut as key and its position as value



        HashMap<Character, Integer> map = new HashMap<Character, Integer>();



        for (int i = 0; i < nuts.length; i++) {



            map.put(nuts[i], i);



        }








        //for each bolt , check for the nut in map



        for (int i = 0; i < bolts.length; i++) {



            char bolt = bolts[i];



            if (map.containsKey(bolt)) {



                nuts[i] = bolts[i];



            } else {



                System.out.println("for bolt " + bolt + " no nut is present.");



                return;



            }



        }



        System.out.println("(Hash Map) Matched nuts and bolts are: ");



        System.out.println(Arrays.toString(nuts));



        System.out.println(Arrays.toString(bolts));



    }








    public static void main(String[] args) {



        char[] nuts = {'$', '%', '&', 'x', '@'};



        char[] bolts = {'%', '@', 'x', '$', '&'};



        match(nuts, bolts);



    }



}





        view raw

        NutsAndBoltsHashMap.java

        hosted with ❤ by GitHub
      


Run Code

Output:

Reference - http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/

, '&'}
Output:

Matched nuts and bolts are:

[$, %, &, *, x]
[$, %, &, *, x]
Approach:
Brute Force –
Compare each nut (or key) will all the bolts (or locks) till we do not find the match.
Time Complexity: O(n2)
Code: Run Code










import java.util.Arrays;








public class NutsAndBoltsBruteForce {








    public static void match(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(Arrays.toString(nuts));



        System.out.println(Arrays.toString(bolts));



    }








    public static void swap(char [] bolts, int i, int j){



        char temp = bolts[i];



        bolts[i] = bolts[j];



        bolts[j] = temp;



    }



    



    public static void main(String[] args) {



        char [] nuts = {'$', '%', '&', 'x', '@'};



        char [] bolts = {'%', '@', 'x', '$', '&'};



        match(nuts,bolts);



    }



}





        view raw

        NutsAndBoltsBruteForce.java

        hosted with ❤ by GitHub
      


Run Code

Use Hash Map:

Insert all the nuts as key and its position as value into Hash Map.
Iterate through all the bolts and check for the nuts in the hash map and put it into the right place.

Code: Run Code










import java.util.Arrays;



import java.util.HashMap;








public class NutsAndBoltsHashMap {








    public static void match(char[] nuts, char[] bolts) {



        //Create a HashMap for nuts, nut as key and its position as value



        HashMap<Character, Integer> map = new HashMap<Character, Integer>();



        for (int i = 0; i < nuts.length; i++) {



            map.put(nuts[i], i);



        }








        //for each bolt , check for the nut in map



        for (int i = 0; i < bolts.length; i++) {



            char bolt = bolts[i];



            if (map.containsKey(bolt)) {



                nuts[i] = bolts[i];



            } else {



                System.out.println("for bolt " + bolt + " no nut is present.");



                return;



            }



        }



        System.out.println("(Hash Map) Matched nuts and bolts are: ");



        System.out.println(Arrays.toString(nuts));



        System.out.println(Arrays.toString(bolts));



    }








    public static void main(String[] args) {



        char[] nuts = {'$', '%', '&', 'x', '@'};



        char[] bolts = {'%', '@', 'x', '$', '&'};



        match(nuts, bolts);



    }



}





        view raw

        NutsAndBoltsHashMap.java

        hosted with ❤ by GitHub
      


Run Code

Output:

Reference – http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/
Related Posts:
Social Network Problem
Minimum number of adjacent swaps to sort the given array
Candidate Voting Problem
Minimum No of operations required to convert a given number to 1 - Integer…
Efficient Robot Problem - Find Minimum Trips
Given an array, find all unique subsets with a given sum with allowed repeated digits.
Find all possible combinations with sum K from a given number N(1 to N) with the…
Non-decreasing Array with one allowed change
Lexicographically next permutation With One swap
Lexicographically previous permutation With One swap
Design data structure for players and ranks
Find subarray with a sum to given number-2 | Handle negative numbers
Generate all the strings of length n from 0 to k-1.
Max Flow Problem - Ford-Fulkerson Algorithm
Activity Selection Problem