Infosys SP/DSE || OA Problems || July 2025 ✅

In the enchanted forest, Pious found a straight magical vine with N glowing berries of different colors: The colours of berries are represented by lowercase letters such that Magical Vine[i] represents the colour of the berry i.

Pious wanted to gather the first few berries from the vine to craft a special bracelet for his best friend, Gala.

Gala loves symmetric patterns, so Pious wants the berries on the bracelet to follow a repeating design. A sequence of berries S is considered magical if it can be represented as:

S = P+Q+P+Q+P+...+P+Q+P

where:

• P and Q are berry color sequences.

• The sequence must have (2K + 1) parts, with (K + 1) copies of P and K copies of Q placed alternately.

• Either P or Q (or both) can be empty.

Pious needs your help to figure out which initial segments of the vine form a magical pattern and how many magical segments are possible.

Find the total number of ways in which Pious can cut the first few berries from the branch such that they form a magical pattern.

Input Format

The first line contains an integer, N, denoting the number of berries on the vine.

The next line contains an integer, K, described in the problem.

The next line contains a string, Magical, Vine, denoting the colors of all the berries.

Constraints

1 <= N <= 10^6

1 <= K <= 10^6

N <= len(Magical Vine) <= N

Sample Test Cases Case 1

Input 4 1 abcd

Output 4

Explanation N=7, K=2

s = "pqpqpqp"

The magical sequence can be the first 4 berries: "papa"

We can take P = "", Q = "pq"

→ P appears 3 times (K+1), Q appears 2 times (K)

The magical sequence can be the first 5 berries: "pqpqp"

We can take P = "p", Q = "q" → P appears 3 times (K+1), Q appears 2 times (K)

The magical sequence can be the first 6 berries: "pqpqpq"

We can take P = "pq", Q = ""

→ P appears 3 times (K+1), Q appears 2 times (K)

So, 3 ways are possible.

Case 2

Input 7 2 xyzxyz

Output 1

Case 3

Input 7 2 pqpqpqp

Output 3

public class Solution {
    public static int Gala_Pious(int N, int K, String Magical_Vine) {
        // Write your code here
    }
}

You are given an array A of length N. The value of a subsegment is calculated by multiplying all the values in that subsegment, for example the value of (2, 3, 5) is 2 * 3 * 5 = 30.

Find the total number of ways to partition the array A into consecutive subsegments that cover all elements such that the value of each subsegment is divisible by at least X factors. Since the number of ways can be large, return it modulo 10^9 + 7.

Input Format

The first line contains an integer N, denoting the number of elements in A.

The next line contains an integer X, denoting the number of factors the value of a subsegment must have.

Each of the next N subsequent lines (where 0 <= i < N) contains an integer describing A[i].

Constraints

1 <= N <= 10^5 2 <= X <= 10^5 1 <= A[i] <= 10^5

Sample Test Cases Case 1

Input 2 2 2 2

Output 2

Explanation N=2, X=2, A=[2, 2]

There are two ways to partition the array:

• [2], [2]. Product of each = 2, which has factors {1, 2}.

• [2, 2]. Product is 4. The number of factors of 4 is more than 2.

Case 2

Input 3 5 2 6 8

Output 1

Explanation A=[2,6,8], N=3, X=5

The only way is to take the whole array as a single subsegment.

2 * 6 * 8 = 96. Number of factors of 96 is more than 5.

Case 3

Input 5 3 2 2 3 2 2

Output 3

Explanation N=5, X=3, A=[2, 2, 3, 2, 2]

There are three ways to partition this array:

• [2, 2, 3], [2, 2]

• [2, 2], [3, 2, 2]

• [2, 2, 3, 2, 2]

public class Solution {
    public static int getCount(int N, int X, List<Integer> A) {
        // Write your code here
    }
}

The kingdom of Eldoria was a land of unity, where its N sacred cities were connected through a vast network of enchanted bridges. Each city was a stronghold of knowledge and power.

However, an ancient saga shattered the harmony of Eldoria, causing the bridges to break randomly and leaving the kingdom divided into isolated regions.

The Great Oracle of Eldoria has foreseen a way to restore balance. He must study every possible subset of cities and count the total number of ways they can be split into exactly X isolated realms, where X is a prime number.

For every prime number X from 1 to N, the Oracle must:

• Determine the number of ways to choose a non-empty group of cities such that the bridges between them create exactly X separate connected realms.

• Sum up all prime values of X that contribute to the valid configurations.

Find the total number of valid ways for each prime number X from 1 to N.

Input Format

The first line contains an integer N, denoting the number of cities.

Each of the next N subsequent lines (where 1 ≤ i ≤ N) contains an integer describing Cities[i].

Constraints

1 <= N <= 5000 1 <= Cities[i] < i

Sample Test Cases Case 1

Input 3 -1 1 1

Output 1

Explanation N=3, Cities=[-1,1,1] For prime X=2: result=1 For prime X=3: result=0 Only subset {2,1} forms exactly 2 connected components. Total = 1.

Case 2

Input 4 -1 1 1 1

Output 4

Explanation N=4, Cities=[-1,1,1,1] X=2, result=3 (subsets: (2,3), (2,4), (3,4)) X=3, result=1 (subset: (2,3,4)) Total=3+1=4.

Case 3

Input 4 -1 1 2 1

Output 5

Explanation N=4, Cities=[-1,1,2,1] X=2, result=5 (subsets: (1,3), (2,4), (3,4), (1,3,4), (2,3,4)) X=3, result=0 Total=5+0=5.