Colorful Numbers | Algorithms

Colorful Numbers | Algorithms
Objec­tive: Given a num­ber, find out whether its col­or­ful or not.
Col­or­ful Num­ber: When in a given num­ber, prod­uct of every digit of a sub-sequence are dif­fer­ent. That num­ber is called Col­or­ful Num­ber. See Example

Example:
Given Number : 3245
Output : Colorful
Number 3245 can be broken into parts like 3 2 4 5 32 24 45 324 245.
this number is a colorful number, since product of every digit of a sub-sequence are different.
That is, 3 2 4 5 (3*2)=6 (2*4)=8 (4*5)=20, (3*2*4)= 24 (2*4*5)= 40

Given Number : 326
Output : Not Colorful.
326 is not a colorful number as it generates 3 2 6 (3*2)=6 (2*6)=12

• Insert all the dig­its into hast table
• Cre­ate a pow­er­set of dig­its except empty set (Power Set)
• Mul­ti­ply all the dig­its in the indi­vid­ual pow­er­set and insert into Hash Table.
• If any point, num­ber already present in the Hash table, return false
• No need to use hashtmap, hashset will just work.

    Hashtable<Integer, Integer> ht = new Hashtable<>(); // use hashmap or just hashset.

    boolean [] used; // for creating powerset, every digit, either

                         //it will be selected or not

    public int [] getdigits(int Number){

        int length = String.valueOf(Number).length();

        int A [] = new int [length];

        int counter = length-1; //start filling from the end

        while(Number>0){

            int x = Number%10;

            Number = Number/10;

            A[counter]=x;

            counter--;

        }

        return A;

    }

    public boolean getColorFul(int Number){

        ht.clear();

        int [] A = getdigits(Number);

        used = new boolean[A.length];      

        return powerSet(A, used, 0);

    }

    public boolean powerSet(int [] A, boolean [] used, int x){

        if(x==used.length-1){

            used[x] = false;

            boolean b = insertInHash(A, used);

            if(b){

                used[x] = true;

                return insertInHash(A, used);

            }else{

                return false;

            }

        }

        used[x] = false;

        boolean p = powerSet(A, used, x+1);

        used[x] = true;    

        return p & powerSet(A, used, x+1);

    }

    public boolean insertInHash(int [] A, boolean [] used){

        int Sum=0;

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

            if(used[i]){

                if(Sum==0){

                    Sum =A[i];

                }

                else{

                    Sum*=A[i];

                }

                 

            }

        }

        if(ht.containsKey(Sum)){           

            return false;

        }else{

            ht.put(Sum, 1);

            return true;

        }

         

    }

Read full article from Colorful Numbers | Algorithms