Finding prime numbers (with.Java)
This is an article about the problem of finding prime numbers (with.Java).
I would like to solve the coding test problem and reflect on the problem I solved.
Letβs get to the problem first.
Problem
Pieces of paper with single digits are scattered.
Iβm trying to figure out how many primes I can make by attaching scattered pieces of paper.
Given the string numbers written on each piece of paper, complete the solution function so that you can return how many prime numbers can be made from the piece of paper.
Restrictions
- Numbers are strings that are greater than or equal to 1 and less than or equal to 7.
- Numbers consist of only numbers from 0 to 9.
- β013β means that there are scattered pieces of paper with the numbers 0, 1, and 3.
Input/Output Examples
numbers | return |
---|---|
β17β | 3 |
β011β | 2 |
my solution to the problem
import java.util.Set;
import java.util.HashSet;
class Solution {
private Set<Integer> numSet = new HashSet();
public int solution(String numbers) {
char[] numArr = numbers.toCharArray();
for(int i = 1; i <= numArr.length; i++)
makeCase(numArr, 0, i, new int[numArr.length], new boolean[numArr.length]);
return numSet.size();
}
private void makeCase(char[] numArr, int cnt, int size, int[] idxArr, boolean[] visit){
if(cnt == size){
String numStr = "";
for(int i = 0; i < size; i++) numStr += numArr[idxArr[i]];
int num = Integer.parseInt(numStr);
if(isPrime(num)) numSet.add(num);
return;
}
for(int i = 0; i < numArr.length; i++){
if(!visit[i]){
visit[i] = true; idxArr[cnt] = i;
makeCase(numArr, cnt+1, size, idxArr, visit);
visit[i] = false;
}
}
}
private boolean isPrime(int n){
if(n < 2) return false;
for(int i = 2; i <= Math.sqrt(n); i++)
if(n % i == 0) return false;
return true;
}
}
Solution Description
- The solution method takes string numbers as input.
- Split each number by converting the numbers into a character array.
- Invoke the makeCase method to generate all possible combinations with each number.
- The makeCase method is recursively called and uses backtracking to generate all possible combinations.
- Within the makeCase method, use an array idxArr that stores the currently selected index and an array visit that indicates if that index has been visited.
- After each combination is completed, determine if the number is prime and add it to the numSet.
- The isPrime method determines whether a given number is a prime number.
- After all combination creation has been completed, return the size of the numSet to obtain a prime number.
Conclusion
This code solves the problem of using backtracking to generate all possible combinations with a given number, and returning the number of prime numbers among them.