Objective: 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:Use Hash Map:This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
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); } }
- 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.
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); | |
} | |
} |
(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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} |
Output:
Reference – http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/