Testing 4 numbers to see if its has 3 unique numbers

Question

I'm having a little trouble wrapping my head around this logic and thought I had a fix but am stumped now.

The goal is to create a 4 digit pin and have 3 unique numbers and 1 can be a duplicate. They can be in any order as well. Here is what i have so far:

boolean UniqueNums(String nums)
{
    for (int i=0; i < 3; i++)
        for (int j=i+1; j < 3; j++)
            if (nums.charAt(i) == nums.charAt(j))
                return false;

    // If no duplicate characters encountered,
    // return true
    return true;
}

So if i pass the numbers 1137 it fails but other like 1371 pass.

I feel this is the different then the linked duplicate answer link, due to im not trying to do it in one line and I'm not just counting the number of times the number occurs. More a long the lines of validating the values being passed.

Any help or advice would be appreciated.

Answer 1

What about:

boolean UniqueNums(String data) {
    Set<Character> found = new HashSet<>();
    int count = 0;
    for (char c : data.toCharArray()) {
        boolean noClash = found.add(c);

        count += (noClash ? 0 : 1);
        if (count == 2) {
            return false;
        }
    }

    return true;
}

• 1234 returns true (no duplicate)
• 1231 returns true (a single duplicate)
• 1221 returns false (a pair of duplicates)
• 1112 returns false (a number used more than twice)

It also works if your PIN is longer then 4 characters, it only requires a single loop making it O(n), and it fails fast

Answer 2

Instead of nested for loops (with complexity O(n^2)), you can use hashing to count the occurrences of each digit and then check for valid pin number. Here is algorithm:

static boolean UniqueNums(String digit){
    int array[] = new int[10];
    for (int i=0;i<digit.length();i++){
        array[digit.charAt(i)-48]++;  //48 because ascii of 0 is 48
    }
    //Now check for frequency
    int count = 0;
    for (int i=0;i<10;i++){
       if(array[i] > 2) return false;
       if(array[i] == 2){
          ++count;
       }
     }
     if(count <= 1) return true;
     return false;
}

This will be of O(k), where k is number of digits in your number.

Answer 3

Because of the numeric limitations involved, your predicate can be reduced from:

a 4 digit pin and have 3 unique numbers and 1 can be a duplicate. they can be in any order as well.

to

have 3 unique characters

(Your code doesn't test for digits and length so I assume some other code does that.)

boolean hasAtLeastThreeUniqueCharacters = "1123".codePoints().distinct().count() >= 3;

Answer 4

I think keeping counters in a Map is simpler:

public boolean UniqueNums(String pin){

    if(pin.length() > 4) {
        //pin too long
        return false;
    }

    Map<Character, Integer> counters = new HashMap<>();
    for(int i = 0; i < pin.length(); i++){

        Character c = pin.charAt(i);
        if(!Character.isDigit(c)){
            //not a number.
            return false;
        }

        counters.put(c, counters.getOrDefault(c,0) + 1);
        if(counters.get(i) > 2){
            // digit appear 3 times.
            return false;
        }
    }

    if(counters.keySet().size() < pin.length() - 1){
        // not 3 unique numbers e.g 1122
        return false;
    }

    return true;
}

Answer 5

You only need one additional int to maintain bit mask for each of the digits. A short would do but it gets widened to int in Integer.bitCount() call either way.

boolean uniqueNums(String nums) {
  int pin = Integer.parseInt(nums);
  int mask = 0;
  for (int i = 0; i < nums.length(); i++) {
    mask |= 1 << pin % 10;
    pin /= 10;
  }
  return Integer.bitCount(mask) >= 3;
}

resulting in

uniqueNums("1234") // true
uniqueNums("9393") // false

Answer 6

You could also group numbers by occurrences, filter those which are at most 2 occurrences and so that their count could be as long as num length, or length - 1 (one duplicate) :

boolean atMostOneOneDuplicate(String num) {
     long occurences = num.chars()
        .mapToObj(i -> (char) i)
        .collect(Collectors.groupingBy(c -> c, Collectors.counting()))
        .entrySet()
        .stream()
        .map(Map.Entry::getValue)
        .filter(v -> v < 3)
        .count();

    return occurences == num.length() || occurences == num.length() - 1;

}

Answer 7

Use a map to keep track of occurances

import java.util.HashMap;
import java.util.Map;

class Main{
    public static void main(String[] args) {
        System.out.println(isValid("1137"));
        System.out.println(isValid("1371"));
        System.out.println(isValid("1234"));
        System.out.println(isValid("1222"));
    }
    public static boolean isValid(String num){
         Map<Character,Integer> digitsWithNumberOfOccurances = new HashMap<>();
         int numOfDigitsThatOccuredTwice = 0;
         for(int i = 0; i < num.length(); i++){
             char currentChar = num.charAt(i);
             int currentNumberOfOccurences = digitsWithNumberOfOccurances.getOrDefault(currentChar,0);
             currentNumberOfOccurences ++;
             digitsWithNumberOfOccurances.put(currentChar,currentNumberOfOccurences);
             if(currentNumberOfOccurences == 2){
                 numOfDigitsThatOccuredTwice++;
                 // only one digit can occur twice
                 if(numOfDigitsThatOccuredTwice > 1) {
                     return false;
                 }
             }else if(currentNumberOfOccurences > 2){ // no digit can occur more than twice
                 return false;
             }
         }
        return true;
    }
}