DCA Previous Years Sample Questions

DCA Sheet

Problem Statement

We are given a string A and we need to find the number of different substrings of A that are fake palindromes. A substring is a contiguous sequence of characters within a string.

A string is called a palindrome if it reads the same backwards as forwards. For example, "MADAM" is a palindrome because if we reverse it, we get "MADAM" again. A fake palindrome is a string that is not necessarily a palindrome itself, but one of its permutations is a palindrome. For example, the string "AAC" is a fake palindrome because one of its permutations, "ACA", is a palindrome. However, the string "ACD" is not a fake palindrome because none of its permutations are palindromes.

To solve this problem, we need to iterate over all possible substrings of A, and for each substring, check if it is a fake palindrome. To check if a substring is a fake palindrome, we need to check if any of its permutations is a palindrome. We can do this by generating all permutations of the substring and checking each one to see if it is a palindrome. However, generating all permutations of a string can be very expensive in terms of time and memory, especially for long strings. So, we need to find a more efficient way to check if a substring is a fake palindrome.

One approach is to use a frequency table to count the number of occurrences of each character in the substring. If a substring has at most one character with an odd frequency count, then it can be rearranged into a palindrome. This is because we can place the character with the odd frequency count in the middle of the palindrome, and the rest of the characters on either side of it. Using this approach, we can check each substring in O(n^2) time, where n is the length of the string. For each substring, we count the frequency of each character and check if at most one character has an odd frequency count. If this is true, then we add the substring to our count of fake palindromes.

Input Format:
First line contains a string S
Output Format:
Print a single integer (number of fake palindrome sub-strings).
Constraints:
1 <= |S| <= 2 * 105
The string will contain only Upper case 'A' to 'Z'
Sample Input 1:
ABAB
Sample Output 1:
7
Explanation:
The fake palindrome for the string ABAB are A, B, A, B, ABA, BAB, ABAB.
Sample Input 2:
AAA
Sample output 2:
6
Explanation:
The fake palindrome for the string AAA are A, A, A, AA, AA, AA

  1. Python Code
    
def count_fake_palindromes(s):
    n = len(s)
    count = 0
    for i in range(n):
        freq = {}
        for j in range(i, n):
            c = s[j]
            freq[c] = freq.get(c, 0) + 1
            odd_count = sum(1 for val in freq.values() if val % 2 == 1)
            if odd_count <= 1:
                count += 1
    return count

# Example usage:
s = 'ABAB'
print(count_fake_palindromes(s))  # Output: 7
  1. Java Code
    
    import java.util.*;

    public class FakePalindromeSubstring {
    
        public static int countFakePalindromes(String s) {
            int n = s.length();
            int count = 0;
            for (int i = 0; i < n; i++) {
                Map freq = new HashMap<>();
                for (int j = i; j < n; j++) {
                    char c = s.charAt(j);
                    freq.put(c, freq.getOrDefault(c, 0) + 1);
                    int oddCount = 0;
                    for (int val : freq.values()) {
                        if (val % 2 == 1) {
                            oddCount++;
                        }
                    }
                    if (oddCount <= 1) {
                        count++;
                    }
                }
            }
            return count;
        }
    
        public static void main(String[] args) {
            String s = "ABAB";
            System.out.println(countFakePalindromes(s));  // Output: 7
        }
    }

Problem Statement

In network marketing, a person who sells some merchandise becomes the root node of a network marketing tree. The first person who inducts someone into the network marketing tree becomes the supervisor. If this new recruit inducts a third person into the network marketing tree, the new recruit becomes the supervisor of the third person, and so on. Whenever anybody in the network marketing tree makes a profit, they have to pass a certain percentage of that profit to their supervisor. The percentage of the profit passed to the supervisor will be rounded to the nearest integer, and hence will always be an integer at each level.

Now, we need to calculate the profit of the person at the root of the network marketing tree coming from a particular individual at the Nth level in the tree. Let's assume that the profit earned by the person at the Nth level is P. We also know that each person in the network marketing tree passes a certain percentage of their profit to their supervisor. Let's assume that the percentage of profit passed from each person to their supervisor is R. Now, we can write the following equation:

Profit at root node = P * (1 - R/100) ^ N

Here, (1 - R/100) is the fraction of the profit retained by each person after passing on the percentage R to their supervisor. Raised to the power of N, this gives us the fraction of the original profit that is retained by the person at the Nth level, which is then multiplied by P to give us the final profit earned by the person at the root node. We can use this equation to calculate the profit earned by the person at the root node coming from any particular individual in the network marketing tree.


Sample Input:

Input has three lines, each with one integer.
The first line contains an integer N, which describes the height of the network marketing tree.
The second line contains an integer M, which denotesthe profit earned by particular individual at Nth level.
The third line contains an integer P, which denotes profit % that needsto be passed on to the supervisor. Each supervisor will always get an integer amount of profit from his subordinate.
Output:
The profit earned by the person at the root of the network marketing tree coming from a particular individual at Nth level in the tree.
Example:
Input:
3
100
10
Output:
1
Explanation:
We are given N=3, M=100 and P=10
The person is at 3 rd level of hierarchy earned 100 as profit.
The person at 2 nd level will get P% of profit of person at 3 rd level. 10%of 100=10
The person at first level(root) will earn P% profit of person at 2 nd level. 10%of 10=1

  1. Python Code
    
def calculate_profit(n: int, m: int, p: int) -> int:
    # Base case
    if n == 1:
        return m

    # Recursion to calculate the profit earned by supervisor
    supervisor_profit = calculate_profit(n - 1, m, p)

    # Calculate the profit earned by the person at root
    root_profit = (supervisor_profit * p) // 100

    return root_profit

# Example usage:
n = 3
m = 100
p = 10
print(calculate_profit(n, m, p))  # Output: 1
  1. Java Code
    
    import java.util.*;

    public class Main {
    
        public static int calculateProfit(int n, int m, int p) {
            // Base case
            if (n == 1) {
                return m;
            }
    
            // Recursion to calculate the profit earned by supervisor
            int supervisorProfit = calculateProfit(n - 1, m, p);
    
            // Calculate the profit earned by the person at root
            int rootProfit = (supervisorProfit * p) / 100;
    
            return rootProfit;
        }
    
        public static void main(String[] args) {
            int n = 4;
            int m = 2000;
            int p = 50;
    
            System.out.println(calculateProfit(n, m, p)); // Output: 250
        }
    }

Problem Statement

The problem describes a situation where a plumber needs to check if a pipe junction is balanced or not. A pipe junction is balanced if the sum of actual capacities of all incoming pipes is equal to the sum of actual capacities of all outgoing pipes. However, if the junction is not balanced, the plumber needs to add either an input pipe or an output pipe to balance it.

Each pipe has a rated capacity and an actual capacity. The actual capacity of a pipe is lower than the rated capacity by a rust factor R, which depends on the material of the pipe. For example, if a pipe has a rated capacity of 65 and the rust factor is 2, then its actual capacity would be 63.

If the combined actual capacity of all incoming pipes is more than the combined actual capacity of all outgoing pipes, then the plumber needs to add an outgoing pipe. On the other hand, if the combined actual capacity of all incoming pipes is less than the combined actual capacity of all outgoing pipes, then the plumber needs to add an incoming pipe. If an outgoing pipe is added, its rated capacity is denoted as a negative number, and if an incoming pipe is added, its rated capacity is denoted as a positive number.

In summary, the plumber needs to check if a pipe junction is balanced or not, and if it is not balanced, then they need to add a pipe to balance it. The rated capacity of the added pipe depends on whether it is an incoming pipe or an outgoing pipe.

Input:
The input has three lines.
The first line contains three space generated integers N M R denoting the number of incoming pipes, outgoing pipes and rust factor respectively.
The second line contains N space separated integers denoting the rated capacity of each incoming pipe.
The third line contains M space separated integers denoting the rated capacity of each outgoing pipe.
Output:
Print the rated capacity of the pipe required to balance the junction or print “BALANCED” if the junction is already balanced


Input:
3 3 2
85 75 95
70 80 45

Output:
-62

Input:
5 6 1
10 26 33 40 50
20 7 53 25 45 10

Output:
BALANCED

Explanation:
There are 3 input pipes, 3 output pipes and the rust factor is 2.
The rated capacities of the input pipe are 85,75 and 95 respectively.
The rated capacities of the output pipe are 70, 80 and 45 respectively.
Here, it will be required to add an outgoing pipe with rated capacity 62. Hence the output is -62

  1. Python Code
    
n, m, r = map(int, input().split())
in_caps = list(map(int, input().split()))
out_caps = list(map(int, input().split()))

in_total = sum([(cap - r) for cap in in_caps])
out_total = sum([(cap - r) for cap in out_caps])

if in_total == out_total:
    print("BALANCED")
elif in_total > out_total:
    capacity = in_total - out_total + r
    print(-1 * capacity)
else:
    capacity = out_total - in_total + r
    print(capacity)
  1. Java Code
    
    import java.util.Scanner;

    public class PipeJunction {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); // number of incoming pipes
            int m = sc.nextInt(); // number of outgoing pipes
            int r = sc.nextInt(); // rust factor
            int inSum = 0; // sum of actual capacities of input pipes
            int outSum = 0; // sum of actual capacities of output pipes
            
            // calculate sum of actual capacities of input pipes
            for (int i = 0; i < n; i++) {
                int ratedCap = sc.nextInt(); // rated capacity of pipe
                int actualCap = ratedCap - r; // actual capacity of pipe
                inSum += actualCap;
            }
            
            // calculate sum of actual capacities of output pipes
            for (int i = 0; i < m; i++) {
                int ratedCap = sc.nextInt(); // rated capacity of pipe
                int actualCap = ratedCap - r; // actual capacity of pipe
                outSum += actualCap;
            }
            
            // check if the junction is balanced
            if (inSum == outSum) {
                System.out.println("BALANCED");
            } else {
                int diff = Math.abs(inSum - outSum); // difference in actual capacities
                int capacity = diff + r; // rated capacity of pipe to be added
                
                if (inSum > outSum) { // add an outgoing pipe
                    capacity = -capacity; // denote outgoing pipe with negative rated capacity
                }
                
                System.out.println(capacity);
            }
            
            sc.close();
        }
    }

Problem Statement

The problem at hand is to help a traveler plan their journey from Pune to Ahmedabad. The traveler intends to use a GPS system to find all possible paths from Pune to Ahmedabad. Once all the possible paths are found, the traveler wants to know the smallest and second smallest distance between Pune and Ahmedabad. The reason for this is that the traveler wants to choose the smallest or second smallest path to start their journey.

To solve this problem, we can start by creating a list of all possible paths from Pune to Ahmedabad, and the corresponding distances for each of these paths. Once we have this list, we can sort the distances in ascending order and return the first and second distances from the sorted list. These will be the smallest and second smallest distances respectively.
Let's assume that the percentage of profit passed from each person to their supervisor is R. Now, we can write the following equation:


Input:
1. The first input contains N, total number of paths from source to destination.
2. The second input contains N sorted integers separated by newline
A1,A2,….An; representing the distance of all paths.
Output:
Output contains two numbers separated by single space character.
If all paths are equal, then the system should generate a message as “Equal”.
If N is less than 2, then the system should generate a message as “Invalid input”.
Constraints:
2 < N <= 10
1 <= A[I] <= 100
Input

4
100
400
300
250

Output
100 250
Explanation: Out of given 4 possible paths only 100 and 250 are the smallest distances
to reach the destination.
Input:

1
200
Output:

Invalid Input
Input:
3
100
100
100

Output:
Equal

  1. Python Code
    
n = int(input())
distances = [int(input()) for _ in range(n)]

if n < 2:
    print("Invalid input")
elif len(set(distances)) == 1:
    print("Equal")
else:
    sorted_distances = sorted(set(distances))
    print(sorted_distances[0], sorted_distances[1])
  1. Java Code
    
        import java.util.*;

        public class Main {
            public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                int[] distances = new int[n];
                for (int i = 0; i < n; i++) {
                    distances[i] = sc.nextInt();
                }
                Arrays.sort(distances);
                if (n < 2) {
                    System.out.println("Invalid input");
                } else if (distances[0] == distances[n - 1]) {
                    System.out.println("Equal");
                } else {
                    System.out.println(distances[0] + " " + distances[1]);
                }
            }
        }

Problem Statement

The game development company wants to create a brain game application for kids that involves several tasks. One of the tasks in the game requires the player to replace each digit of a given number with another digit. To do this, the game provides a table that maps each existing digit (0 to 9) to a replacement digit (9 to 0). For example, if the given number is 1234, the player needs to replace each digit with the corresponding digit from the table, resulting in the number 8765. The game may present multiple numbers for the player to modify, and the player's score will be based on the accuracy and speed of their replacements.

Existing Digit: 0 1 2 3 4 5 6 7 8 9

Replace By: 9 8 7 6 5 4 3 2 1 0
Constraints:
0 <= N <= 1000000
The system should generate a message as “Wrong Input” if the value of N is out of range.
Sample Example: Sample Example:
Input:

105201

Output:

894798

  1. Python Code
    
num = int(input("Enter a number: "))
new_num = 0
i = 0
while num > 0:
    digit = num % 10
    num //= 10
    new_digit = 9 - digit
    new_num += new_digit * (10 ** i)
    i += 1
if new_num > 1000000:
    print("Wrong Input")
else:
    print("New number:", new_num)
  1. Java Code
    
        import java.util.Scanner;

        public class Main {
            public static void main(String[] args) {
                Scanner scanner = new Scanner(System.in);
                System.out.print("Enter a number: ");
                String input = scanner.nextLine();
                
                int n = input.length();
                char[] output = new char[n];
                
                for (int i = 0; i < n; i++) {
                    char c = input.charAt(i);
                    if (c >= '0' && c <= '9') {
                        int digit = c - '0';
                        int newDigit = 9 - digit;
                        output[i] = (char) (newDigit + '0');
                    } else {
                        System.out.println("Wrong Input");
                        return;
                    }
                }
                
                System.out.println("Replaced number: " + new String(output));
            }
        }