Count the prime groups-CodePudding

Given an input string of digits, split that into groups of prime numbers by maintaining the order given in the input string and each group should hold all the characters of the input string. Find the count of such groups.

Example:

Ans:

Explanation:

The 3 combinations are [11,37,5], [11,3,7,5] and [113,7,5]

Code that I tried

public int countPossibilities(String s) {
    int n = s.length();
    int[] ar = new int[n   1];
    ar[0] = 1;
    for (int i = 1; i < n; i  ) {
        int j = i - 1;
        while (j >= 0 && j >= i - 3) {
            if (prime(s.substring(j, i)))
                ar[i]  = ar[j];

            j--;
        }
    }

    return ar[n];
}

public boolean prime(String s) {
    int n = Integer.parseInt(s);
    if (n < 2) return false;

    for (int i = 2; i * i <= n; i  )
        if (n % i == 0) return false;

    return true;
}

This works fine if the input string length is small.

But the length of the input string can be from 1 to 10^5. So my program fails for large strings.

Example:

1350297079989171477791892123929141605573631151125933376097791877830238462471373933362476484818693477173990672289892448124097556197582379957168911392680312103962394732707409889862447273901522659

Expected result is : 4386816

What is the right approach to solve this problem.

CodePudding user response：

Here's working Python code that answers your long example.

Let dp[i] represent the number of valid combinations ending at the ith index of the input. Then for each prime suffix of length x ending at input[i], we add to dp[i] the count of valid combinations ending at dp[i-x], provided there is also a count of valid combinations recorded for dp[i-x].

# https://rosettacode.org/wiki/Sieve_of_Eratosthenes
def primes2(limit):
    if limit < 2: return []
    if limit < 3: return [2]
    lmtbf = (limit - 3) // 2
    buf = [True] * (lmtbf   1)
    for i in range((int(limit ** 0.5) - 3) // 2   1):
        if buf[i]:
            p = i   i   3
            s = p * (i   1)   i
            buf[s::p] = [False] * ((lmtbf - s) // p   1)
    return set(["2"]   [str(i   i   3) for i, v in enumerate(buf) if v])

def f(n):
  k = 6
  primes = primes2(10**k)
  dp = [0] * len(n)   [1]
  for i in range(len(n)):
    suffix = ""
    for j in range(min(i   1, k)):
      suffix = n[i-j]   suffix
      if suffix in primes and dp[i-j-1] > 0:
        dp[i]  = dp[i-j-1]
  return dp[len(n) - 1]

Output:

n = "1350297079989171477791892123929141605573631151125933376097791877830238462471373933362476484818693477173990672289892448124097556197582379957168911392680312103962394732707409889862447273901522659"

print(f(n)) # 4386816

CodePudding user response：

Proof of concept from my comments, but in C# (I'm an AP Comp Sci teacher that doesn't like to code in Java; go figure!):

Take the length of the input string minus 1 and call this "padLength". Now raise 2 to the power of padLength to get the total number of possibilities for string combinations; call this number "numberOfCombinations". Next, count from 0 to numberOfCombinations and convert that decimal number to a BINARY number, left padded with zeroes out to padLength, called "binaryNumber". The binary number represents whether or not a space should be added in-between the digits of the original number. For instance, binary "1100" and dec "11375" would result in "1 1 375" because 1 means put a space in-between. This process will give you all combinations of the original string in the different groups. Then you can extract the numbers from the groups and see if they are primes...

Code:

private async void button1_Click(object sender, EventArgs e)
{
    if (textBox1.Text.Trim().Length == 0) { return; }

    textBox1.Enabled = false;
    button1.Enabled = false;
    textBox2.Clear();

    String binary;
    StringBuilder sb = new StringBuilder();
    String input = textBox1.Text.Trim();
    char[] digits = input.ToCharArray();
    int padLength = input.Length - 1;
    long combinations = (long)Math.Pow(2, padLength);

    List<String> combos = new List<string>();
    await Task.Run(() => {
        for (long i = 0; i < combinations; i  )
        {
            binary = Convert.ToString(i, 2).ToString().PadLeft(padLength, '0');
            char[] binaryDigits = binary.ToCharArray();

            sb.Clear();
            for (int s = 0; s < digits.Length; s  )
            {
                sb.Append(digits[s]);
                if (s < (digits.Length - 1))
                {
                    if (binaryDigits[s] == '1')
                    {
                        sb.Append(' ');
                    }
                }
            }

            combos.Add(sb.ToString());
        }
    });
    
    textBox2.Lines = combos.ToArray();
    textBox1.Enabled = true;
    button1.Enabled = true;
}

Output:

For very large inputs, you won't be able to compute the number of combinations using Math.Pow(), or any built-in methods for converting a decimal to a binary number. In those cases, you can "count manually" in binary by using a String directly and following the counting algorithm. You'd build the binary numbers using only String manipulation directly by inspecting each char to see if it is 1 or 0 and acting accordingly. You'll know you're done when you have a string of ones that has a length one less than the length of your input. It will run a lot slower than working with numbers directly.