Blog

Problem 1:

Problem Description

In the Faculty of Informatics Engineering, the Teacher of Mathematics gave a lecture on bits and explained XOR and OR.

Then he decided to test the competence of his student by giving them questions. He will give the student an array A of N numbers and then give them Q queries. Each query will consist of three numbers Type_i, L_i, and R_i. Each of the queries can be one of the following types:

• If Type; is 1, then the student has to replace each A_i with (A_i|(A_i – 1)) for every i between Li and Ri.
• If Type; is 2, then the student has to replace each A_i with (A_i^(A_i – 1)) for every i between Li and Ri.

After each query, the professor asks his students to calculate the sum of the numbers of array A. You need to find the sum of the answers to all queries modulo 10^9+7.

Notes:

• The sign | represent the logical OR
• The sign ^ represent the logical XOR.

Constraints

• • 1 SNS 10^5
• • 1sQs 10^5
• • 1 s A[i] = 10^5
• • 1 s Type[i] s2
• • 1 sl[i] SN
• • 1 SR[i] SN

Input Format For Custom Testing

The first line contains an integer, N, denoting the number of elements in A.
The next line contains an integer, Q, denoting the number of the query (the number of the elements in arrays Type, Land R).
Each line i of the N subsequent lines (where 0 si< N) contains an integer describing A[i].
Each line i of the Q subsequent lines (where 0 si<Q) contains an integer describing Type[i].
Each line i of the Q subsequent lines (where 0 si<Q) contains an integer describing L[i].
Each line i of the Q subsequent lines (where 0 si<Q) contains an integer describing R[i].

INPUT/OUTPUT

Input
4
1
1
2
3
4
1
2
3
Output
11
Input
4 1 1 2 3 4 2 2 3
Output
9
Input
2 5 4 8 6 1 2 1 2 3 2
Output
60

Problem 2:

Problem Description:

A professor explained the meaning of palindrome string to his students. He then gave his students a string S consisting of lower case letters and asked them to split it into as many palindromes strings as possible such that the length of each string was greater than 2.

However, Ali misunderstood the meaning of palindrome string to be a string where the first letter is equal to the last letter of the string. Ali then went to solve the problem given by
the professor based on what he understood. Therefore Ali split the string into the largest number of substrings that have a length greater than 2 and each substring has the first letter
last letter

Your task is to find the largest number of strings that Ali will get. If there is no solution print -1.

Note: When we split a string S into substrings each character of S will belong to exactly one of these substrings.

Constraints

1 <= len(S) <= 10^5

Sample Cases

Input
xxxx
Output
2
Input
abccdba
Output
1
Input
abactczz
Output
3

Problem 3:

Problem Description:

There are N houses and K different languages spoken in a city. The language is spoken by the occupant of the of the occupant of the houses can be represented as an array of N elements A1, A2, ……. An. Such that each element represents the language spoken by the occupant of the corresponding house.

In order to create a more structured city plan, the city council decided to make all the people who spoke the same language live as close as possible to each other Thus, the city council came up with a method to move any two adjacent houses. In other words, the government can swap house number i with house number i+1 or with house number i-1 (if it does exist).

However, the city council does not want to make any unnecessary moves since it is expensive to swap the positions of two houses.

The city council requests you to help find the minimum swaps needed in order to achieve the optimal arrangement of the houses of the residents. Since the answer can be very large modulo 10^9+7.

Notes:

Each distinct value of Ai represents a distinct language while exactly the same values of Ai represent the same language.

Constraints

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

Input Format For Custom Testing

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

Sample Cases

Input
4 3 1 3 3 2
Output
0
Input
5 2 1 2 1 2 1
Output
3
Input
6 3 1 3 2 1 2 3
Output
4

Accenture Associate Software Engineer Hiring- August Coding Question & Answer!