Unique digits sequence in Java

2 min read 464 words

Table of Contents

The challenge

Consider the following series:

0,1,2,3,4,5,6,7,8,9,10,22,11,20,13,24...There is nothing special between numbers `` and 10.

Let’s start with the number 10 and derive the sequence. 10 has digits 1 and . The next possible number that does not have a `1` or a  is 22. All other numbers between 10 and 22 have a 1 or a ``.

From 22, the next number that does not have a 2 is 11. Note that 30 is also a possibility because it is the next higher number that does not have a 2, but we must select the lowest number that fits and is not already in the sequence.

From 11, the next lowest number that does not have a 1 is 20.

From 20, the next lowest number that does not have a 2 or a `` is 13, then 24 , then 15 and so on.

Once a number appers in the series, it cannot appear again.

You will be given an index number and your task will return the element at that position. See test cases for more examples.

Note that the test range is n <= 500.

The solution in Java code

Option 1:

import java.util.ArrayList;

class Solution{
    public static boolean uniqDigits(int a, int b){   
        String c  = a + "";
        String d  = b + "";        
        for (int i = 0; i < d.length(); ++i)         
            if (c.indexOf(d.charAt(i)) != -1) return false;          
        return true;
    }


    public static int findNum(int n){  
        ArrayList<Integer> v = new ArrayList<>(); v.add(0);
        int i = 1, cur = 0;
        while (++i <= n+1){
            int next = 0;             
            while (!uniqDigits(next, cur) || v.contains(next)) {
                next++;                
            }
            v.add(next);
            cur = next;    
        }         
        return v.get(v.size()-1);
    }
}

Option 2:

import java.util.*;
class Solution{
    public static int findNum(int n) {
      System.out.println(n);
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 1; i < 1000; i++) {
            arrayList.add(i);
        }
        
        ArrayList<Integer> finalArray = new ArrayList<>();
        finalArray.add(0);
        M1:
        for (int i = 0; finalArray.size() < n+1;) {
            String[] strings = Integer.toString(arrayList.get(i)).split("", 0);
            
            for (String s : strings) {
                if (Integer.toString(finalArray.get(finalArray.size()-1)).contains(s)) {
                    i++;
                    continue M1;
                }
            }
            if (!finalArray.contains(arrayList.get(i))) {
                finalArray.add(arrayList.get(i));
                arrayList.remove(i);
                i = 0;
            }
            
        }
        Iterator<Integer> iterator = finalArray.iterator();
        for (int i = 0; i < finalArray.size() - 1; i++) {
            iterator.next();
        }
        return iterator.next();
    }
}

Option 3:

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
import java.util.function.Predicate;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

class Solution{
    public static int findNum(int n){
        Set<String> set =
                IntStream.rangeClosed(0, 1000)
                        .mapToObj(Integer::toString)
                        .collect(Collectors.toCollection(() -> new TreeSet<>(Comparator.comparing(Integer::parseInt))));
        String res = "1";
        for (int i = 0; i <=n; i++) {
            Pattern pattern = Pattern.compile(String.format("[%s]", res));
            res = set.stream().filter(Predicate.not(j -> pattern.matcher(j).find())).findFirst().get();
            set.remove(res);
        }
        return Integer.parseInt(res);
    }
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;

public class SolutionTest{    
    @Test
    public void basicTests(){     
        assertEquals(1,Solution.findNum(1));
        assertEquals(5,Solution.findNum(5));
        assertEquals(22,Solution.findNum(11));
        assertEquals(103,Solution.findNum(100));
        assertEquals(476,Solution.findNum(500));   
    }
}
Tags:
Andrew
Andrew

Andrew is a visionary software engineer and DevOps expert with a proven track record of delivering cutting-edge solutions that drive innovation at Ataiva.com. As a leader on numerous high-profile projects, Andrew brings his exceptional technical expertise and collaborative leadership skills to the table, fostering a culture of agility and excellence within the team. With a passion for architecting scalable systems, automating workflows, and empowering teams, Andrew is a sought-after authority in the field of software development and DevOps.

Tags

Recent Posts