You wrote down many positive integers in a string called num. However, you realized that you forgot to add commas to seperate the different numbers. You remember that the list of integers was non-decreasing and that no integer had leading zeros.

Return the number of possible lists of integers that you could have written down to get the string num. Since the answer may be large, return it modulo 109 + 7.

Input: num = "327" Output: 2 Explanation: You could have written down the numbers: 3, 27 327

Input: num = "094" Output: 0 Explanation: No numbers can have leading zeros and all numbers must be positive.

Input: num = "0" Output: 0 Explanation: No numbers can have leading zeros and all numbers must be positive.

Constraints:

1 <= num.length <= 3500 num consists of digits '0' through '9'.

Hi I have used mcm variation in this where i will traverse the depending on the condition wheather if i put comma then this particular string is equal or greater then previous but my dp storage is not getting optimized please help me out!!

Your code here...

class Solution {
    public static int numberOfCombinations(String num) {
        HashMap<String,Integer> t= new HashMap<String,Integer>();
        return mcm_noOfComb("0",num,t);
    }
    public static int mcm_noOfComb(String s1,String s2,HashMap<String,Integer> t)
    {
        if(s2.length()==0)
            return 1;
        if(s2.charAt(0)=='0' || s2.length()<s1.length())
            return 0;
        if(s2.length()==s1.length())
        {
            int i=0;
            while(i<s1.length())
            {
                if(s2.charAt(i)<s1.charAt(i))
                {
                    return 0;
                }
            }
        }
        String key=s2;
        if(t.containsKey(key))
            return t.get(key);
        int k=0;
        while(k<s1.length())
        {    if(s2.charAt(k)<s1.charAt(k))
        {
            k=s1.length()+1;
            break;
        }
            k++;
        }
        int mod=(int)1e9+7;
        int cnt=0;
        for(int i=k;i<=s2.length();i++)
        {
            int temp = mcm_noOfComb(s2.substring(0,i),s2.substring(i,s2.length()),t)%mod;
            cnt = ((cnt%mod)+(temp%mod))%mod;
        }
        t.put(key,cnt);
        return cnt;
    }
}

Please provide the approach of the following ,I have tried but i didn't came up with a good approach

You are given an array A of length N and an integer K. It is given that a number m is called special if gcd(m,Aj) = 1 for all 0<=j<N

Let R be an array containing all special number in the range [ 1 , K ] inclusive in sorted order . Your task is to return R.

Note : A follows 0-based indexing.

Input Format The first line contains an integer N , denoting the number of elements in A. The next line contains an integer K , denoting the given integer. Each line i of the N subsequent lines (where 0<=i<N) contains an integer describing A[i].

Constraints 1<=N<=10^5 1<=K<=10^5 1<=A[i]<=10^5

Sample Input Sample Output 3 1 5 5 1 2 3

4 1 5 2 3 4 3 5 7

4 1 1 1 1 1 1