Accenture OA (Cognitive and Technical Assessment 2023) - Questions and Answers

14387

C Python Java Algorithm Data Structure Array Interview

Accenture conducted its Cognitive and Technical Assessment on June 26, 2023, which included multiple programming-related questions.
During the Coding assessment, each participant was tasked with solving two coding-related questions from the following list:
Here are the questions that were asked during the assessment along with their answers(mainly consist of brute-force approach):
(Comment down how we can optimised it);

1. Special Numbers
2. Add Alternate Nodes in Linked List
3. Distinct and Duplicate Integers
4. Lettered Number
5. Evaluate the given expression
6. Maximum Element And Its Index
7. Fine Number
8. Mearge and Rearrange
9. Sum of digits
10. Small Number Problem
11. Marching People
12. Number of Cards
13. Ball and Box Problem
14. Maximum revenue garage
15.Sum of Numbers
16. Decryt the string

Question 1: Special Numbers

Problem Statement
you are given a function:

int  DesiredArray(int Arr, int N, int k):

The function accepts an array 'Arr' of size 'N' and an integer 'k'.
You have to find the 'K' smallest integers that are not divisible by any of the 'N' integers and return the sum of all 'K' integers.

Note:

Array won't conatin 1.

Example:
Input:

K: 4
N: 5
Arr: [2,3,4,5,6]

Output:

Explanation:

First, K smallest non-divisible by Arr_i integers will be 1, 7, 11, 13. Hence the sum will be 32.

The custom input format for the above case:

5 4
2 3 4 5 6

(The first line represents 'N' and 'K', the second line represents the element of the array 'Arr')

Sample input

K:  4
N:  4
Arr : [3,6,9,12]

Sample Output

The custom input format for the above case:

4  4
3 6  9 12

(The first line represents 'N' and 'K', the second line represents the element of the array 'Arr')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution:

1. Brute Force Solution:

a. Intuition:

The code aims to find the K smallest integers that are not divisible by any of the N integers. It uses a brute force approach to iterate through numbers and checks divisibility using the isDivisible function.

b. Approach

The isDivisible function checks whether a number is divisible by any of the given divisors.
The DesiredArray function takes the array of divisors, sorts them, and initializes the sum, number, and count variables.
It iterates through numbers starting from 1 until the count of desired integers reaches K.
For each number, it checks if it is not divisible by any of the divisors. If true, it adds the number to the sum and increments the count.
Finally, it returns the sum.

c. Time Complexity:
The time complexity of the code is O(K * N log N) because of sorting the divisors array.

d. Space Complexity:
The space complexity of the code is O(N) for storing the divisors array.

Code:

C++ Code:

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool isDivisible(int num, const vector<int>& divisors) {
    for (int divisor : divisors) {
        if (num % divisor == 0) {
            return true;
        }
    }
    return false;
}

int DesiredArray(int* Arr, int N, int K) {
    vector<int> divisors(Arr, Arr + N);
    sort(divisors.begin(), divisors.end());

    int sum = 0;
    int num = 1;
    int count = 0;

    while (count < K) {
        if (!isDivisible(num, divisors)) {
            sum += num;
            count++;
        }
        num++;
    }

    return sum;
}

int main() {
    int testcases;
    cin>>testcases;
   // while(testcases--){
            int N, K;
            cin >> N >> K;

            int* Arr = new int[N];
            for (int i = 0; i < N; i++) {
                    cin >> Arr[i];
                 }

           int result = DesiredArray(Arr, N, K);
            cout << result << endl;

         delete[] Arr;
   // }
    return 0;
}

Java Code:

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static boolean isDivisible(int num, int[] divisors) {
        for (int divisor : divisors) {
            if (num % divisor == 0) {
                return true;
            }
        }
        return false;
    }

    public static int desiredArray(int[] arr, int N, int K) {
        int[] divisors = Arrays.copyOf(arr, N);
        Arrays.sort(divisors);

        int sum = 0;
        int num = 1;
        int count = 0;

        while (count < K) {
            if (!isDivisible(num, divisors)) {
                sum += num;
                count++;
            }
            num++;
        }

        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testcases = scanner.nextInt();

      //  while (testcases-- > 0) {
            int N = scanner.nextInt();
            int K = scanner.nextInt();

            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = scanner.nextInt();
            }

            int result = desiredArray(arr, N, K);
            System.out.println(result);
       // }
    }
}

Python

def is_divisible(num, divisors):
    for divisor in divisors:
        if num % divisor == 0:
            return True
    return False

def desired_array(arr, N, K):
    divisors = sorted(arr)

    sum = 0
    num = 1
    count = 0

    while count < K:
        if not is_divisible(num, divisors):
            sum += num
            count += 1
        num += 1

    return sum

testcases = int(input())

for _ in range(testcases):
    N, K = map(int, input().split())
    arr = list(map(int, input().split()))

    result = desired_array(arr, N, K)
    print(result)

2. Another Solution

a. Approach:
The code follows a brute-force approach to solve the problem.

It iterates over numbers starting from 1 until it finds K non-divisible integers.
For each number, it checks divisibility by iterating through the array 'Arr' and breaks the inner loop if a divisor is found.
If no divisors are found, the number is considered non-divisible and added to the 'nonDivisible' set.
Finally, the code calculates the sum of the non-divisible integers and returns it.

c. Time Complexity:
The time complexity of the code is O(K * N), where K is the number of desired non-divisible integers and N is the size of 'Arr'. This is because for each candidate number, the code iterates through all the elements in 'Arr' to check for divisibility.

d. Space Complexity:
The space complexity of the code is O(K), where K is the number of desired non-divisible integers. This is because it uses an unordered set ('nonDivisible') to store the non-divisible numbers, which can have a maximum size of K.

Overall, the code employs a straightforward approach to solve the problem but may not be the most efficient solution. It checks divisibility for each number individually, which can lead to longer execution times for larger inputs. Consideration of more optimized algorithms or number theory principles can improve the efficiency of the solution.

Code:

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int DesiredArray(int* Arr, int N, int K) {
    unordered_set<int> nonDivisible;

    for (int i = 1; nonDivisible.size() < K; i++) {
        bool divisible = false;
        for (int j = 0; j < N && Arr[j] * Arr[j] <= i; j++) {
            if (i % Arr[j] == 0) {
                divisible = true;
                break;
            }
        }
        if (!divisible) {
            nonDivisible.insert(i);
        }
    }

    int sum = 0;
    for (int num : nonDivisible) {
        sum += num;
    }

    return sum;
}

int main() {
    int testcases;
    cin >> testcases;

   // while (testcases--) {
        int N, K;
        cin >> N >> K;

        int* Arr = new int[N];
        for (int i = 0; i < N; i++) {
            cin >> Arr[i];
        }

        int result = DesiredArray(Arr, N, K);
        cout << result << endl;

        delete[] Arr;
   // }

    return 0;
}

2. Add Alternate Nodes in Linked List

Problem Statement

There is a singly linked list represented by the following structure:

struct node
{
   int data;
   struct Node* next;
};

Implement the following function:

struct Node* AddAlternateNodes(struct Node* head);

The function accepts a pointer to the start of the linked list , 'head' as its argument . Implement the function to modify the given list in such a way that origin added to the value of next to the next node and return the modified list.

Note:

Return null if list is null, In case of python if list is None return None.
Do not create new linked list , just modify the input linked list
1st and 2nd node values remain unchanged

Example:
Input:

head: 1-> 2 -> 3 -> 4 -> 5 -> 6 -> 7

Output:

1 -> 2 -> 4 -> 6 -> 8 -> 10 -> 12

Explanation:

Adding original value of the node to its next to next node,
Replace value of '3' with 1 + 3 = 4
Replace value of '4' with 2 + 4 = 6
Replace value of '5' with 3 + 5 = 8
Replace value of '6' with 4 + 6 = 10
Replace value of '7' with 5 + 7 = 12
Thus obtained linked list is 1 -> 2 -> 4 -> 6 -> 8 -> 10 ->12

The custom input format for the above case:

7
1 2 3 4 5 6 7

(The first line represents the number of nodes, the second line represents the linked list)

Sample input:

head : 2 -> 1 -> 9 -> 2

Sample output:

2 -> 1 -> 11 -> 3

The custom input format for the above case:

4
2 1 9 2

(The first line represents the number of nodes, the second line represents the linked list)

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition

The code is designed to modify a singly linked list as follows:

For each node in the list (except the first two nodes), add the value of the current node to the value of the next to next node and update the value of the current node with the sum.

b. Approach

Class Definition:
A class ListNode is defined to represent a node in a singly linked list. Each node contains an integer value val and a pointer to the next node next.
Creating a Linked List from an Array:
createLinkedListFromArray function takes a vector of integers arr and creates a linked list from it. It returns a pointer to the head of the linked list.
Modifying the Linked List:
addAlternateNodes function takes the head of a linked list as input.
It iterates through the list starting from the second node.
For each node, it calculates the sum of the current node's value and the value of the next to next node, and updates the current node's value with this sum.
Displaying the Linked List:
displayLinkedList function takes the head of a linked list as input and prints out the values of all the nodes.
Main Function:
In the main function, a vector arr is initialized with some values.
createLinkedListFromArray is used to create a linked list from this vector.
addAlternateNodes is called to modify the linked list.
Finally, displayLinkedList is called to print out the modified linked list.

c. Time complexity:

Creating the linked list from an array takes O(n) time, where n is the length of the array.
Modifying the linked list also takes O(n) time, as we are traversing the list once.
Displaying the linked list takes O(n) time.
Overall, the time complexity of the code is O(n).

d. Space complexity

The space complexity is O(n) as we are creating a linked list of size n, where n is the length of the array.

Code:

C++


// Definition of the Node structure
struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

// Function to create a linked list from an array
Node* createLinkedListFromArray(vector<int>& arr) {
    if (arr.empty()) {
        return nullptr;
    }

    Node* dummy = new Node(-1);
    Node* temp = new Node(arr[0]);
    dummy->next = temp;

    for (int i = 1; i < arr.size(); i++) {
        temp->next = new Node(arr[i]);
        temp = temp->next;
    }

    return dummy->next;
}

// Function to add alternate nodes
void addAlternateNodes(Node* head) {
    if (head == nullptr) return;

    Node* current = head->next;
    int prevVal, currVal, nextVal;
    prevVal = head->val;
    currVal = current->val;

    while (current != nullptr && current->next != nullptr) {
        current = current->next;
        nextVal = current->val;
        current->val = prevVal + nextVal;
        prevVal = currVal;
        currVal = nextVal;
    }
}

// Function to display the linked list
void displayLinkedList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
}

// Main function
int main() {
    int n; cin>>n;
    vector<int> arr(n);
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    Node* head = createLinkedListFromArray(arr);
    addAlternateNodes(head);
    displayLinkedList(head);

    return 0;
}

3. Distinct and Duplicate Integers

Problem Statement

Implement the following function:

def AddDistinctDuplicate(a,b,c,d):

The function accepts four integers 'a','b','c' and 'd' as its argument . Implement the function to find the sum of distinct numbers and subtract the duplicate number and return the difference (sum of distinct number - duplicate number).

For sum of distinct number add all number that appears only once
For duplicate number subtract the duplicate number only once
Notes: All computed values lie within integer range

Examples:

Input:

a:5
b:4
c:4
d:9

Output

Explanation:

2 distinct number are 5 and 9. Sum of distinct number = 5+9 = 14. Duplicate number = 4. Difference = Sum of distinct numbers - Duplicate number = 14 - 4 = 10. Thus, output is 10.

The custom input format for the above case:

(The first line represent 'a'. the second line represent 'b', the third line represent 'c', the fourth line represent 'd')
Sampe input

a: -1
b:  3
c:  8
d: -6

Sample Output

The custom input format for the above case:

(The first line represent 'a'. the second line represent 'b', the third line represent 'c', the fourth line represent 'd')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition
The code aims to find the sum of distinct numbers and subtract the duplicate number from it. To achieve this, it utilizes an unordered set data structure to track the distinct numbers encountered. By inserting each element into the set, it identifies whether the number is distinct or a duplicate.

b. Approach:

Create an empty unordered set called distinct_nums to store the distinct numbers.
Initialize variables distinct_sum to keep track of the sum of distinct numbers and duplicate to store the duplicate number.
For each input element a, b, c, and d:
Check if the element can be inserted into the distinct_nums set using insert().
If the element can be inserted (i.e., it is distinct), add it to the distinct_sum.
If the element cannot be inserted (i.e., it is a duplicate), assign it as the duplicate number.
Calculate the difference between the distinct_sum and the duplicate number.
Return the calculated difference as the result.

c. Time and Space Complexity:

Time Complexity:
The code iterates over the input elements once, performing insertions and lookups in the unordered set. Since the number of elements is fixed (4 in this case), the time complexity is O(1).
Space Complexity:
The code uses an unordered set to store the distinct numbers. In the worst case, all elements are distinct, resulting in a space complexity of O(4), which simplifies to O(1).
Overall, the approach has constant time complexity and space complexity, making it very efficient for this specific problem. The use of the unordered set allows for efficient lookup and insertion operations, ensuring the uniqueness of the distinct numbers.

Code:

C++

#include <unordered_set>
using namespace std;

int AddDistinctDuplicate(int a, int b, int c, int d) {
    unordered_set<int> distinct_nums;
    int distinct_sum = 0;
    int duplicate = 0;

    // Check for distinct numbers and calculate their sum
    if (distinct_nums.insert(a).second) {
        distinct_sum += a;
    } else {
        duplicate = a;
    }

    if (distinct_nums.insert(b).second) {
        distinct_sum += b;
    } else {
        duplicate = b;
    }

    if (distinct_nums.insert(c).second) {
        distinct_sum += c;
    } else {
        duplicate = c;
    }

    if (distinct_nums.insert(d).second) {
        distinct_sum += d;
    } else {
        duplicate = d;
    }

    return distinct_sum - duplicate;
}

Another Approach

a. Intuition:

The problem requires finding the sum of distinct numbers and subtracting the duplicate number from it. To solve this, the code utilizes a map data structure to count the frequencies of the input elements. By iterating over the elements, it determines which numbers are distinct and calculates their sum, while also identifying the duplicate number to subtract it later.

b. Approach:

Create an empty map called frequency to store the frequencies of the elements.
Iterate over the input elements a, b, c, and d.
For each element:
Check if it exists as a key in the frequency map.

If it exists, increment its corresponding value (frequency) by 1.
If it doesn't exist, add it to the frequency map with a frequency of 1.
Initialize variables distinct_sum to keep track of the sum of distinct numbers and duplicate to store the duplicate number.
Iterate over the frequency map:
For each element:
If its frequency is 1, add the element to the distinct_sum.
If its frequency is greater than 1, assign it as the duplicate number.
Calculate the difference between the distinct_sum and the duplicate number.
Return the calculated difference as the result

c. Time and Space Complexity:

Time Complexity:
The code iterates over the input elements once, resulting in a time complexity of O(1) since the number of elements is fixed (4 in this case).
Space Complexity:
The code uses a map to store the frequencies of the elements. In the worst case, there can be 4 distinct elements, resulting in a space complexity of O(4), which simplifies to O(1).
Overall, the approach has constant time complexity and space complexity, making it very efficient for this specific problem.

C++

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int AddDistinctDuplicate(int a, int b, int c, int d) {
    vector<int> elements = {a, b, c, d};
    map<int, int> frequency;

    // Store element frequencies in the map
    for (int element : elements) {
        frequency[element]++;
    }

    int distinct_sum = 0;
    int duplicate = 0;

    // Calculate sum of distinct numbers and find the duplicate
    for (const auto& entry : frequency) {
        if (entry.second == 1) {
            distinct_sum += entry.first;
        } else {
            duplicate = entry.first;
        }
    }

    return distinct_sum - duplicate;
}

int main() {
    int a, b, c, d;

    // Read inputs
    cin >> a >> b >> c >> d;

    // Calculate the result
    int result = AddDistinctDuplicate(a, b, c, d);

    // Print the result
    cout << result << endl;

    return 0;
}

Python3

def AddDistinctDuplicate(a, b, c, d):
    elements = [a, b, c, d]
    frequency = {}

    # Store element frequencies in the dictionary
    for element in elements:
        frequency[element] = frequency.get(element, 0) + 1

    distinct_sum = 0
    duplicate = 0

    # Calculate sum of distinct numbers and find the duplicate
    for entry in frequency.items():
        if entry[1] == 1:
            distinct_sum += entry[0]
        else:
            duplicate = entry[0]

    return distinct_sum - duplicate


# Main function
if __name__ == "__main__":
    a = int(input())
    b = int(input())
    c = int(input())
    d = int(input())

    # Calculate the result
    result = AddDistinctDuplicate(a, b, c, d)

    # Print the result
    print(result)

4. Lettered Number

Problem Statement:

you are required to implement the follwing function:

int LetteredNumberSum(char[] str, int len);

The function accepts string 'str' ('str1' in case of Python) as its argument. Implement the function which returns sum of number equivalents of each letter in the given string 'str'.
The number equivalents are as follows:

A = 1
B = 10
C = 100
D = 1000
E = 10000
F = 100000
G = 1000000

Assumption: 'str' contains upper case letters only
Note:
Number equivalent for any letter other than (A,B,C,D,E,F,G) is 0
Computed value lies with in integer range
Return 0 if 'str' is null (None, in case of Python)

Example:

Input:

DCCBAA

Output:

Explanation:

Sum = 1000 + 100 + 100 + 10 + 1 + 1 = 1212

The custom input format for the above case:

 6 
 DCCBAA

(The first line represents the length of the string, the second line represents the string)

Sample input

GBCE

Sample Output

The custom input format for the above case:

  4
  GBCE

(The first line represents the length of the string, the second line represents the string)

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition

The function LetteredNumberSum aims to calculate the sum of number equivalents of each letter in a given string. Each letter corresponds to a specific number value, and the task is to accumulate the sum of these number values.

b. Approach:

Iterate through each character in the input string.
For each character, use a switch statement to determine its corresponding number value.
Accumulate the number values in a variable sum.
Return the final sum.

c. Time and Space Complexity:

The time complexity of this function is O(n), where n is the length of the input string. This is because we need to iterate through each character in the string once.

The space complexity is O(1) since we only use a constant amount of additional space to store the sum and other variables.

Code

C++
#include <iostream>
using namespace std;

int LetteredNumberSum(char* str, int len) {
    if (str == nullptr) {
        return 0;
    }

    int sum = 0;

    for (int i = 0; i < len; i++) {
        char letter = str[i];
        int ans = 0;

        switch (letter) {
            case 'A':
                ans = 1;
                break;
            case 'B':
                ans = 10;
                break;
            case 'C':
                ans = 100;
                break;
            case 'D':
                ans = 1000;
                break;
            case 'E':
                ans = 10000;
                break;
            case 'F':
                ans = 100000;
                break;
            case 'G':
                ans = 1000000;
                break;
            default:
                ans = 0;
                break;
        }

        sum += ans;
    }

    return sum;
}

int main() {
    char str[] = "GBCE";
    int len = sizeof(str) - 1;

    int result = LetteredNumberSum(str, len);

    cout << "Sum: " << result << endl;

    return 0;
}

5. Evaluate the given expression

Problem Statement

You are given a funtion,

int  EvaluateExpression(char* expr);

The function accepts a mathematical expression 'expr' as parameter. Implement the function to evaluate the given expression 'expr' and return the evaluated value.

Assumption:

You can assume there is no space in between any of the characters of expression 'expr'.
Expression 'expr' contains only digits and operators (+, -, * and /).

Note:

Every operation should be integer based e.g.: 5/2 should give 2 not 2.5
Consider the precedence of operators while evaluating the expression, precedence of ('/' or '*') > precedence of ('+; or '-').
if 'expr' has multiple operators of same precedence then evaluate them from left to right.

Example:

Input:

expr : 2+3+5*4/2

Output:

Explanation:

2 + 3 + 5 * 4/2 = 2 + 3 + 10 = 15, hence 15 is the evaluated value.

The custom input format for the above case:

9
2 + 3+ 5* 4/2

(The first line represents the length of the string, the second line represents the string)

Sample input

expr: 22 +15 - 2*7/3

Sample Output

The custom input format for the above case:

9
22 +15 - 2*7/3

(The first line represents the length of the string, the second line represents the string)

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:

The code aims to evaluate a mathematical expression by following the rules of operator precedence and performing the necessary operations. It uses stacks to store numbers and operators and iterates through the expression character by character.

b. Approach:

The code starts by checking if the input expression is null. It initializes two stacks, one for numbers and another for operators. It then iterates through the expression character by character.
If the current character is a space, it skips to the next character. If it is a digit, it parses the number by continuously multiplying the existing number by 10 and adding the digit value. The parsed number is then pushed onto the numbers stack.
If the current character is an operator, the code handles the precedence of operators. It compares the precedence of the current operator with the operators at the top of the stack.
If the topmost operator has higher precedence, it performs the operation using the top two numbers from the numbers stack and the top operator from the operators stack. The result is then pushed back to the numbers stack. This process continues until the stack is empty or the topmost operator has lower precedence than the current operator. Finally, the current operator is pushed onto the operators stack.
After processing all characters, the code evaluates any remaining operators and numbers by performing the corresponding operations. The final result is obtained from the top of the numbers stack.

c. Time Complexity:

The time complexity of this approach depends on the length of the expression. In the worst case, where the expression contains n characters, the code iterates through each character once. Therefore, the time complexity is O(n).

d. Space Complexity:

The space complexity is determined by the number of operators encountered in the expression. In the worst case, where there are m operators, the code uses two stacks to store the numbers and operators. Therefore, the space complexity is O(m).

Code:

C++

    #include <iostream>
    #include <stack>
    using namespace std;

    int EvaluateExpression(char* expr) {
    if (expr == nullptr) {
        return 0;
      }

    stack<int> numbers;
    stack<char> operators;

    int i = 0;
    while (expr[i] != '\0') {
        if (expr[i] == ' ') {
            // Skip spaces
            i++;
            continue;
        }

        if (isdigit(expr[i])) {
            // If current character is a digit, parse the number
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            numbers.push(num);
        } else {
            // If current character is an operator, handle precedence
            while (!operators.empty() && ((operators.top() == '*' || operators.top() == '/') ||
                   (operators.top() == '+' || operators.top() == '-') && (expr[i] == '+' || expr[i] == '-'))) {
                int num2 = numbers.top();
                numbers.pop();
                int num1 = numbers.top();
                numbers.pop();
                char op = operators.top();
                operators.pop();

                // Perform the operation based on the operator
                int result;
                switch (op) {
                    case '+':
                        result = num1 + num2;
                        break;
                    case '-':
                        result = num1 - num2;
                        break;
                    case '*':
                        result = num1 * num2;
                        break;
                    case '/':
                        result = num1 / num2;
                        break;
                }

                // Push the result back to the numbers stack
                numbers.push(result);
            }

            // Push the current operator to the operators stack
            operators.push(expr[i]);
            i++;
        }
    }

    // Evaluate remaining operators and numbers
    while (!operators.empty()) {
        int num2 = numbers.top();
        numbers.pop();
        int num1 = numbers.top();
        numbers.pop();
        char op = operators.top();
        operators.pop();

        int result;
        switch (op) {
            case '+':
                result = num1 + num2;
                break;
            case '-':
                result = num1 - num2;
                break;
            case '*':
                result = num1 * num2;
                break;
            case '/':
                result = num1 / num2;
                break;
        }

        numbers.push(result);
    }

    // Return the final result
    return numbers.top();
      }

    int main() {
     int length;
    cin >> length;

    char expr[length];
    cin.ignore();
    cin.getline(expr, length + 1);
    int result = EvaluateExpression(expr);
    cout << result << endl;
    return 0;
}

Python

def EvaluateExpression(expr):
    if expr is None:
        return 0

    numbers = []
    operators = []

    i = 0
    while i < len(expr):
        if expr[i] == ' ':
            # Skip spaces
            i += 1
            continue

        if expr[i].isdigit():
            # If current character is a digit, parse the number
            num = 0
            while i < len(expr) and expr[i].isdigit():
                num = num * 10 + int(expr[i])
                i += 1
            numbers.append(num)
        else:
            # If current character is an operator, handle precedence
            while operators and ((operators[-1] == '*' or operators[-1] == '/') or
                   (operators[-1] == '+' or operators[-1] == '-') and (expr[i] == '+' or expr[i] == '-')):
                num2 = numbers.pop()
                num1 = numbers.pop()
                op = operators.pop()

                # Perform the operation based on the operator
                if op == '+':
                    result = num1 + num2
                elif op == '-':
                    result = num1 - num2
                elif op == '*':
                    result = num1 * num2
                elif op == '/':
                    result = num1 // num2

                # Push the result back to the numbers list
                numbers.append(result)

            # Push the current operator to the operators list
            operators.append(expr[i])
            i += 1

    # Evaluate remaining operators and numbers
    while operators:
        num2 = numbers.pop()
        num1 = numbers.pop()
        op = operators.pop()

        if op == '+':
            result = num1 + num2
        elif op == '-':
            result = num1 - num2
        elif op == '*':
            result = num1 * num2
        elif op == '/':
            result = num1 // num2

        numbers.append(result)

    # Return the final result
    return numbers[-1]

length = int(input())
expr = input()
result = EvaluateExpression(expr)
print("Result:", result)

6. Maximum Element And Its Index

Problem Statement:

You are given a function,

Void MaxInArray(int arr[],int length);

The function accepts an integer array 'arr' of size 'length' as its argument. Implement the function to find the maximum element of the array and print the element and its index to the standard output (STDOUT) . The maximum element and its index should be printed in separate lines.

Notes:

Array index start with 0.
Maximum element and its index should be separated by a line in the output.
Assume there is only 1 maximum element in the array.
Print exactly what is asked, do not print any additional greeting messages

Exampe 1:

23 45 82 27 66 12 78 13 71 86

Output:

86
9

Explanation:

86 is the maximum element of array at index 9.

The custon input format for the above case:

10
23 45 82 27 66 12 78 13 71 86

(the first line repersent 'length', the second line repersents the element of the array 'arr')

Example 2:

1 9 11 144 6 7 112 95

Output 2:

144
3

The custom input format for the above case:

8
1 9 11 144 6 7 112 95

(the first line repersent 'length', the second line repersents the elements of the array 'arr')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:

The code aims to find the maximum element in an integer array and its corresponding index.

b. Approach:

The code iterates through the array using a for loop.
It initializes the maximum value (max) as the minimum possible integer value and the index (index) as -1. It compares each element of the array with the current maximum value.
If an element is greater than the current maximum, it updates the maximum value and stores the index of that element.
Finally, it prints the maximum value and the index.

c. Time Complexity:

The time complexity of the code is O(n), where n is the length of the array. This is because it iterates through each element of the array once.

d. Space Complexity:

The space complexity of the code is O(1) because it uses a constant amount of extra space to store the maximum value and the index.

Code


C

void MaxInArray(int arr[], int length){
            int max = INT_MIN, index =-1;
            for(int i =0; i<length; i++){
                              if(arr[i]> max)
                                   {
                                        max = arr[i];
                                        index =i;
                                   }
                            }
         printf("%d\n%d\n", max, index);

    }


Java


class Solution {
    public static void MaxInArray(int[] arr, int length) {
        int max = Integer.MIN_VALUE;
        int index = -1;
        for (int i = 0; i < length; i++) {
            if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        System.out.println(max);
        System.out.println(index);
    }

}

7. Fine Number

Problem Statement

You are given a function:

int FineNumber(int* a, int* b, int n, int m);

The function accepts two arrays 'a' and 'b' of size 'n' and 'm' respectively. Implement the function to compute a fine number and return the same.
A fine number is the greatest number that can be obtained by taking the difference of two numbers such that one of the two numbers is taken from array 'a' and the other is taken from array 'b'.

Example:

Input:

n: 5
m: 6
a: 1 2 3 4 5
b: 10 12 34 2 4 89

Output:

Explanation:

Here, the greatest difference is between a 1 from array 'a' and 89 from array 'b'.

**the custom input format for the above case:

5 6 
1 2 3 4 5 
10 12 34 2 4 89

(The first line represent 'n' and 'm', the second line represents the elements of the array 'a', and the third line represents the elements of the array 'b'.)

Sample input

 n: 4
 m: 3
 a: 6 7 8 11
 b: 3 1 2

Sample output

The custom input format for the above case:

  4 3
  6 7 8 11
  3 1 2

(The first line represent 'n' and 'm', the second line represents the elements of the array 'a', and the third line represents the elements of the array 'b'.)

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

A. Intuition:

The code aims to find the maximum difference between any two numbers, where one number is from vector a and the other number is from vector b.

B. Approach:

The code uses a nested loop to iterate over each pair of numbers, one from vector a and the other from vector b.
It calculates the absolute difference between the two numbers using the abs() function.
It keeps track of the maximum difference (max_diff) seen so far and updates it if the current difference is greater.
Finally, it returns the maximum difference.

C. Time Complexity:

The time complexity of the code is O(n * m), where n is the size of vector a and m is the size of vector b. This is because the code uses nested loops to iterate over all possible pairs of numbers from both vectors.

D. Space Complexity:

The space complexity of the code is O(n + m), where n is the size of vector a and m is the size of vector b. This is because the code uses two additional vectors (a and b) to store the input numbers.

Code

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;
int findFineNumber(int x,vector<int>& a,vector<int>& b) {
    int max_diff = INT_MIN;  // Initialize the maximum difference with negative infinity

    for (int num_a : a) {
        for (int num_b : b) {
            int diff = abs(num_a - num_b);  // Calculate the difference between num_a and num_b
            if (diff > max_diff) {
                max_diff = diff;  // Update the maximum difference if the current difference is greater
            }
        }
    }

    return max_diff;
}

int main() {
    int n ; cin>>n;
    int m ; cin>>m;
    vector<int> a(n),b(m);
    for(int i =0; i<n; i++){
         cin>>a[i];
       }
       for(int i =0; i<m; i++){
    cin>>b[i];
       }


    int result = findFineNumber(n, a, b);
    cout << result <<endl;

    return 0;
}

Java 

class Main {
    public static int findFineNumber(int x, List<Integer> a, List<Integer> b) {
        int max_diff = Integer.MIN_VALUE;  // Initialize the maximum difference with negative infinity

        for (int num_a : a) {
            for (int num_b : b) {
                int diff = Math.abs(num_a - num_b);  // Calculate the difference between num_a and num_b
                if (diff > max_diff) {
                    max_diff = diff;  // Update the maximum difference if the current difference is greater
                }
            }
        }

        return max_diff;
    }

8. Mearge and Rearrange

Problem Statement

You are given a function,

char* MergeStrings(char* str1, char* str2);

The function accepts strings 'str1' and 'str2' as its arguments, Implement the function to generate a string by iterating through each character of given string.

- For i = 0, on comparing charecters at index 0 of input strings, smaller character is placed at index 0 and larger character is placed at index n-1.
- For i = 1, on comparing charecters at index 1 of input strings, smaller character is placed at index 1 and larger character is placed at index n-2.
- For i = k, on comparing charecters at index k of input strings, smaller character is placed at index k and larger character is placed at index n-k-1.
  where k<n and n is the length of output string (Length of string1 + Length of string2).

Assumption: String contain lower case characters only.
Note:

Character 'x' is smaller than 'y' since it occurs prior in alphabetical series.
Return null if both the strings are null.
Return other string if one of the string is null.
Null refers to None in case of Python.
If length of strings is not same, then rest of the characters are added on their original positions.

Example:

Input:

str1: are
str2: denim

Output:

aeeimnrd

Explaination:

Iterations 1 to n( = 4 )

i = 1 : a _ _ _ _ _ _ d (a<d)
i = 2 : a e _ _ _ _ r d (e<r)
i = 3 : a e e _ _ n r d (e<n)
i = 4 : a e e i m n r d

Thus, final output = aeeimnrd

The custum input format for the above case:

3
are
5
denim

(The first line represents the length of the first string 'str1', the second line represents the first string 'str1', the third line represents length of the second string 'str2', the fourth line represents the second string 'str2')

Sample input

 str1:  cape
 str2:  port

Sample Output

capetrop

the custom input format for the above case:

4
cape
4
port

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition
The function named MergeStrings that takes two string inputs str1 and str2. It merges the strings by interleaving their characters based on a specific condition. Here's an explanation of the code:

b. Approach

The function first checks if both str1 and str2 are None. If so, it returns None.
It then checks if str1 is None and returns str2 if that condition is true.
Similarly, it checks if str2 is None and returns str1 if that condition is true.
The lengths of str1 and str2 are stored in variables len1 and len2 respectively.
An empty list named merged is initialized to store the merged characters.
The code enters a while loop with the condition i < len1 and i < len2.
Inside the loop, it compares the characters at index i of str1 and str2.
If str1[i] is less than str2[i], it appends str1[i] followed by str2[i] to the merged list.
Otherwise, it appends str2[i] followed by str1[i] to the merged list.
After appending the characters, it increments i by 1 to move to the next index.
Once the loop is completed, it checks if len1 is less than len2. If true, it extends the merged list with the remaining characters from str2.
Similarly, if len1 is greater than len2, it extends the merged list with the remaining characters from str1.
Finally, it joins the characters in the merged list using the join method with an empty string as the separator.
The merged string is then returned.
In summary, the code merges two strings by interleaving their characters based on the given conditions and returns the merged string.

Time Complexity

The code has a while loop that iterates until the smaller length between len1 and len2 is reached. This loop has a complexity of O(min(len1, len2)) since it depends on the size of the smaller input string.
The code also has two extend operations that append the remaining characters from the longer string to the merged list. These operations have a complexity of O(max(len1, len2) - min(len1, len2)), which is the difference between the lengths of the two input strings.
Lastly, the join operation at the end has a complexity of O(len(merged)) since it concatenates all the characters in the merged list.
Therefore, the overall time complexity of the code can be expressed as O(max(len1, len2)) since the dominant factor is the length of the longer input string.

Space complexity

The code uses a list merged to store the merged string. The maximum size of this list will be the combined length of the two input strings, i.e., len1 + len2. Hence, the space complexity of the code is O(len1 + len2).

In summary, the time complexity is O(max(len1, len2)) and the space complexity is O(len1 + len2).

Code:

Python

def merge_strings(str1, str2):
    if str1 is None and str2 is None:
        return None
    if str1 is None:
        return str2
    if str2 is None:
        return str1

    len1 = len(str1)
    len2 = len(str2)

    merged = []
    i = 0
    while i < len1 and i < len2:
        if str1[i] < str2[i]:
            merged.append(str1[i])
            merged.append(str2[i])
        else:
            merged.append(str2[i])
            merged.append(str1[i])
        i += 1

    if len1 < len2:
        merged.extend(str2[i:])
    elif len1 > len2:
        merged.extend(str1[i:])

    return ''.join(merged)

9. Sum of digits

Problem Statement
You are required to implement the following function:

int DifferenceSumOfDigits(int* arr, int n);

The function accepts an array 'arr' of 'n' positive integers as its argument. Let's suppose:

 f(x) = Sum of digits of an integer

You are required to calculate the value of the following:

F1= [f(arr[0]) + f(arr[1]) + f(arr[2]) + ..........+ f(arr[n-1])] %10
F2 = [(arr[0] + arr[1] + arr[2] + .........+ arr[n-1])] % 10
F = F1 - F2

and return the value of F.

Note: n > 0

Example:

Input:

arr: 11 14 16 10 9 8 24 5 4 3
n: 10

Output:

-4

Explanation:

The value of F1 is (1 + 1) + (1 + 4) + (1 + 6) + (1 + 0) + (9) + (8) + (2 + 4) + (5) + (4) + (3) which is equal to 50 and (50 % 10) is 0 and value of F2 is (11 + 14 + 16 + 10 + 9 + 8 + 24 + 5 + 4 + 3) which is equal to 104 and (104 % 10 ) is 4 , the value of F is (0-4), hence -4 is returned.

The custom input format for the above case:

10
11 14 16 10 9 8 24 5 4 3

(The first line represents 'n', the second line represents the elements of the array 'arr')

Sample input

arr: 16 18 20
n: 3

Sample output:

The custom input format for the above case:

3
16 18 20

(The first line represents 'n', the second line represents the elements of the array 'arr')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:
We calculates the difference between two values, F1 and F2, using a given formula. It involves summing the digits of each element in an array and performing modulo operations to obtain the final difference value.

b. Approach

The sumOfDigits function takes an integer num and calculates the sum of its digits by repeatedly dividing it by 10 and summing the remainders.
The DifferenceSumOfDigits function takes an array arr and its size n as inputs.
It initializes two variables, f1 and f2, to store the cumulative sums of the digit sums and the original values of arr, respectively.
It iterates through each element of arr and updates f1 and f2 accordingly using the sumOfDigits function.
After the loop, it performs modulo 10 operations on both f1 and f2.
It calculates the difference f by subtracting the modulo result of f2 from the modulo result of f1.
The final difference f is returned.
In the main function, user input is taken for the array size n and the elements of arr. Then, the DifferenceSumOfDigits function is called with arr and n, and the result is printed.

c. Time and Space Complexity:

Time Complexity:

The time complexity of the sumOfDigits function is O(log10(num)), where num is the input number. The DifferenceSumOfDigits function iterates through each element of the array once, resulting in a time complexity of O(n). Overall, the time complexity is determined by the larger of these two operations, resulting in O(n) in this case.

Space Complexity:

The space complexity is O(1) as the code uses a fixed amount of memory to store variables regardless of the input size. The space required for arr and other local variables is considered constant.

Code:

C++

#include <iostream>

int sumOfDigits(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int DifferenceSumOfDigits(int arr[], int n) {
    int f1 = 0;
    int f2 = 0;

    for (int i = 0; i < n; i++) {
        f1 += sumOfDigits(arr[i]);
        f2 += arr[i];
    }
      int f = (f1%10) - (f2%10);
    return f;
}

int main() {
    int n;
    std::cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    int result = DifferenceSumOfDigits(arr, n);
    std::cout << result << std::endl;

    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static int sumOfDigits(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public static int differenceSumOfDigits(int[] arr, int n) {
        int f1 = 0;
        int f2 = 0;

        for (int i = 0; i < n; i++) {
            f1 += sumOfDigits(arr[i]);
            f2 += arr[i];
        }

        int f = (f1 % 10) - (f2 % 10);
        return f;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int result = differenceSumOfDigits(arr, n);
        System.out.println(result);
    }
}

10. Small Number Problem

Problem Statement:

Implement the following function:

int *  NextSmallerNumber(int a[], int m);

The function accepts an integer array 'a' of size m. Replace each number of array with nearest smaller number on its right in the array.

Assumption: All integers are > 0.

Note:

Return null if array is null.
Null refers to None in case of Python.
Replace the number with '-1', if no smaller number is present on its right.

Example:

Input:

a: 3 2 11 7 6 5 6 1

Output:

2 1 7 6 5 1 1 -1

Explanation:

Every number is replaced with the 1st smaller number on its right, ('3' -> '2', '2' -> '1', '11' -> '7' , '7' -> '6', '6' ->'5', '5' -> '1', '6' -> '1' and '1' -> '-1'

The custom input format for the above case:

8
3 2 11 7 6 5 6 1

(The first line represent 'm', the second line represent the elements of the array 'a')

Sample input

a: 10 5 4 5 3 2 1

Sample Output

5 4 3 3 2 1 -1

The custom input format for the above case:

7
10 5 4 5 3 2 1

(The fisrt line represent 'm', the second line represents the element of the array 'a')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:

The given code aims to find the next smaller element for each element in the given list a and store the results in another list result.

b. Approach

Initialize a list result with the same size as the input list a, and fill it with -1.
Create an empty stack to store indices of elements from the list a.
Traverse the list a in reverse order (from the last element to the first).
While traversing, pop elements from the stack until the stack is not empty and the current element in the list a is smaller than the element at the top of the stack. This step helps to find the next smaller element for each element in reverse order.
If there are elements remaining in the stack, it means the current element in the list a has a next smaller element, and we update the corresponding position in the result list with the top element of the stack.
Push the current element's index into the stack.
After completing the traversal, the result list will contain the next smaller element for each element in the list a.

c. Time complexity:

The given code traverses the list a once in reverse order. In each iteration, elements are pushed and popped from the stack. The time complexity of this code is O(N), where N is the number of elements in the list a.

d. Space complexity:

The code uses additional space for the result list and the stack. The space complexity is O(N), where N is the number of elements in the list a.

Code

Java:

import java.util.*;

public class NextSmallerNumber {
    public static int[] nextSmallerNumber(int[] a) {
        int n = a.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= a[i]) {
                stack.pop();
            }

            if (!stack.isEmpty()) {
                result[i] = stack.peek();
            }

            stack.push(a[i]);
        }

        return result;
    }

C++

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextSmallerNumber(vector<int>& a) {
    int n = a.size();
    vector<int> result(n, -1);
    stack<int> stack;

    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && stack.top() >= a[i]) {
            stack.pop();
        }

        if (!stack.empty()) {
            result[i] = stack.top();
        }

        stack.push(a[i]);
    }

    return result;
}

int main() {
    int n; cin>>n;
    vector<int>a(n);
    for(int i =0; i<n; i++){
        cin>>a[i];
    }
    vector<int> result = nextSmallerNumber(a);

    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

11. Marching People

Problem Statement:

Infinite number of people are crossing a 2-D plane.They march in such a way that each integral x coordinate will have exactly one person who moves along it in positive y direction, starting form(x,0).

You have to implement the following functions:

int MaximumBarrier(int n, int** barrier);

The function takes an integer matrix 'barrier' having 'n' rows and '3' columns where n denotes the number of barriers. The ith barrier is defined by (xi, yi,di), which means that the barrier is blocking all the people who want to pass through points lying on line segment connecting(xi,yi) and (xi+di,yi). Once a person encounters a barrier, he stops moving.

Given all the barriers, your task is to find the total number of people who will be blocked at some point in their march.

Assumption:

n>0
Length of barrier (d) >0

Notes:

Overlapping of barriers is possible.
Do not use extra memory.

Example:

Input:

n:2
              x    y   d
Barrier 1 :   2    3   3
Barrier 2 :   4    6   4

Output:

Explanation:

1st barrier blocks people of x- coordinates(2,3,4,5), similarly, 2nd barrier blocks people of x-cordinates(4,5,6,7,8), forming a total of '7' blocked people (excluding overlapped values (4,5) for 2nd barrier).

The custom input for the above case:

2
2 3 3
4 6 4

(The first line represents 'n', the next 'n' lines each represent ith barrier.)

Sample input

 n:  3

               x   y  d
   barrier 1:  1   1  2
   barrier 2:  6   5  3
   barrier 3:  11  4  4

Sample Output

The custom input format for the above case:

(The first line represents 'n' , the next 'n' lines each represents i-th barrier.)

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:

The code aims to calculate the total number of y-values that are blocked based on the given barriers. It uses an unordered set to keep track of the unique x-coordinates that are blocked.

b. Approach:

The code iterates through each barrier in the input vector.
For each barrier, it iterates from the starting x-coordinate to the ending x-coordinate (inclusive) and checks if the current x-coordinate is already present in the unordered set.
If not, it adds the x-coordinate to the set.
After processing all the barriers, the code returns the size of the unordered set, which represents the total number of unique x-coordinates that are blocked.

c. Time complexity:

The time complexity of the code is O(n * d), where n is the number of barriers and d is the maximum difference between the starting and ending x-coordinates among all barriers. This is because the code iterates through each barrier and performs an operation for each x-coordinate within the range of the barrier.

d. Space complexity:

The space complexity of the code is O(k), where k is the number of unique x-coordinates that are blocked. The code uses an unordered set to store the blocked x-coordinates, and the size of the set represents the number of unique x-coordinates.

Code


Java:
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int MaximumBarrier(int[][] barrier) {
        Set<Integer> a = new HashSet<>();
        for (int[] i : barrier) {
            for (int j = i[0]; j <= i[0] + i[2]; j++) {
                if (!a.contains(j)) {
                    a.add(j);
                }
            }
        }
        return a.size();
    }
	
C++


#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

int MaximumBarrier(vector<vector<int>>& barrier) {
    unordered_set<int> a;
    for (auto& i : barrier) {
        for (int j = i[0]; j <= i[0] + i[2]; j++) {
            if (a.find(j) == a.end()) {
                a.insert(j);
            }
        }
    }
    return a.size();
}

int main( ) {
    int n; cin>>n;
    vector<vector<int>> barrier = {{2,3,3},{4, 6, 4}};
    int result = MaximumBarrier(barrier);
    cout << result << endl;

    return 0;
}

12. Number of Cards

Problem Statement:

Arrangement of cards used for building pyramids are shown in the followin image:

Figure-1 : Level- 3 Pyramid

Figure -2: Level -2 Pyramid

you are required to implement the following function:

int CardsPyramid(int n);

The function accepts an integer 'n' as an argument. The integer 'n' denotes level of pyramid. You are required to calculate the number of cards. required to build a pyramid of level 'n' and return the number of cards % 1000007.

Note:

Return -1, if 'n' =0

Assumptions:

The number of cards required to build a pyramid of level 1 are 2

Input:

n: 2

Output:

Explaination:

Cards required to build a pyramid of level 1 are 2, adding 1 more level to the pyramid will require 5 more cards, thus a total of 7 cards are needed to build a pyramid of level 2. Hence 7 % 1000007 is returned.

The custum input format for the above case:

(The line represent 'n')

Sample input

 n: 3

Sample Output

The custum input format for the above case:

(The line represent 'n')

Instructions:

This is a templete based question, DO NOT write the "main" function.
your code is judged by an automated system, do not write any additional welcome/greeting messages.
"Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code both in terms of memory and execution time.

Solution

a. Intuition:

The code aims to calculate the number of cards required to build a pyramid of a given level 'n'. The pyramid is built by stacking cards in a specific pattern, and the number of cards needed increases with each level.

b. Approach:

The code uses a simple mathematical formula to calculate the number of cards required. It multiplies the level 'n' by a formula (3 * n + 1) / 2, which represents the number of cards needed for a pyramid of that level. It then returns the result modulo 1000007 to ensure the value stays within a specific range.

c. Time complexity:

The time complexity of the code is O(1) because it performs a constant number of mathematical operations to calculate the result based on the given level 'n'.

d. Space complexity:

The space complexity of the code is O(1) because it does not use any additional data structures or allocate memory dynamically. It only uses a few integer variables to store the input and intermediate results.

Code:

Java

import java.util.Scanner;

public class CardsPyramid {
    public static int calculateCards(int n) {
        if (n == 0) {
            return -1;
        }
        
        int cards = (n * (3 * n + 1)) / 2;
        return cards % 1000007;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int result = calculateCards(n);
        System.out.println(result);
    }
}


C++

#include<iostream>
using namespace std;
int CardsPyramid(int n){
      if(n==0){
       return -1;
     }
      int cards = n*(3* n+1)/2;;
      return cards % 1000007;
}
int main(){
    int n; cin>>n;
    int result = CardsPyramid(n);
    cout<<result<<endl;
 return 0;
}

13. Ball and Box Problem

Problem Statement

Implement the following function:

int NumberOfBalls(int arr[], int n);

The function accepts a non-negative integer array 'arr' of size 'n' as its argument. Every Kth element in the array is the number of balls in the Kth row of a box. Every Kth row of the box needs (K+1)^2 balls, where 0 <= K <= (n-1). Implement the function to find the number of balls required to complete each row of the box and return the total number of balls required.

Assumption: arr[k] <= (k+1)^2

Note:

1. Return -1 if the array is null (or None in the case of Python).
2. Array indexing starts from 0.

Example:

Input:

Arr: 1 2 7 13

Output:

Explanation:

Number of balls each row needs Number of balls each row has
 1 1
 4 2
 9 7
16 13

Total number of balls required = 0 + 2 + 2 + 3 = 7. Thus, the output is 7.

Custom input format for the above case:

4
1 2 7 13

(The first line represents the size of the array, the second line represents the elements of the array)

Sample input:

arr: 0 3 5

Sample Output:

Custom input format for the above case:

3
0 3 5

(The first line represents the size of the array, the second line represents the elements of the array)

Instructions:

This is a template-based question; DO NOT write the "main" function.
Your code is judged by an automated system; do not write any additional welcome/greeting messages.
"Save and test" only checks for basic test cases; more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code in terms of both memory and execution time.

Solution

Intuition:
The code aims to calculate the minimum number of balls needed to complete a set of rows, where each row requires an increasing number of balls. The number of balls needed for a specific row is determined by a mathematical formula. The goal is to calculate the total number of balls needed for all the rows and check if there are enough balls to meet the requirements.

Approach:

The code defines a function NumberOfBalls that takes an integer array arr and an integer n as input. arr represents the number of balls in each row, and n is the size of the array.
Two variables are declared: totalBalls and extraBalls, both of type long long. totalBalls will store the total number of balls required, and extraBalls will keep track of the accumulated balls as we iterate through the rows.
The code uses a for loop to iterate through each row in the array arr.
Inside the loop, the code does the following:
It adds the number of balls in the current row to the extraBalls variable.
It updates the totalBalls variable by adding the value of extraBalls. - This represents the total number of balls required up to the current row.
The code calculates the expected number of balls needed for the current row using the formula (K+1)*(K+2)/2, where K is the current row number (i). This is stored in the expectedBalls variable.
It checks if extraBalls (the actual number of balls) is less than expectedBalls (the expected number of balls for the current row). If this condition is true, it means there are not enough balls to complete the current row, so the function returns -1 to indicate that it's not possible to complete the rows with the given number of balls.
If all rows can be completed with the available balls, the function returns totalBalls, representing the total number of balls required.

Time Complexity:

The time complexity of the code is O(n) because 
- it iterates through the array once, where n is the size of the input array arr. 
- All other operations inside the loop are constant time.

Space Complexity:

The space complexity is O(1) because 
- the code uses a constant amount of additional memory regardless of the size of the input. 
- The memory usage is mainly for the two variables totalBalls and extraBalls, and 
- a few integer variables used for calculations.

Code:

#include <iostream>
using namespace std;

long long NumberOfBalls(int arr[], int n) {
    long long totalBalls = 0;
    long long extraBalls = 0;

    for (int i = 0; i < n; i++) {
        extraBalls += arr[i];  // Add balls in the current row
        totalBalls += extraBalls;  // Update the total balls required

        // Calculate the expected balls needed for the current row
        long long expectedBalls = (1LL * (i + 1) * (i + 2)) / 2;

        if (extraBalls < expectedBalls) {
            // If we don't have enough balls for the current row, return -1
            return -1;
        }
    }

    return totalBalls;
}

int main() {
    int n;
    cin >> n;

    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    long long result = NumberOfBalls(arr, n);
    cout << result << endl;

    return 0;
}

14. Maximum revenue garage

Problem Statement

A garage is represented as:

struct Garage
{
    int bikes;
    int cars;
    int trucks;
};

Implement the function:

int MaxRevenue(struct Garage garages[], int m);

The function accepts an array garages of type Garage, consisting of m elements as its argument. Each element of garages consists of three non-negative integers: bikes, cars, and trucks, referring to the count of bikes, cars, and trucks in a garage, respectively. The cost of servicing a bike, car, and truck are 100, 250, and 500, respectively. Implement the function to calculate revenue generated by each garage and return the maximum revenue generated.

Revenue generated by a garage = (100 * bikes) + (250 * cars) + (500 * trucks)

Note:

1. Computed value lies within the integer range.
2. Return -1 if garages is null (or None in the case of Python).

Example:

Input:

            Bikes:  Cars:   Trucks:
Garage 1:    6        8       2
Garage 2:    5        7       8
Garage 3:   14       10      11
Garage 4:   11       13       5

Output:

Explanation:
The task is to calculate the revenue generated by each garage and return the maximum revenue generated.

Revenue Calculation:

The revenue generated by each garage is calculated using the formula:

Revenue = (100 * Bikes) + (250 * Cars) + (500 * Trucks)

Let's calculate the revenue for each garage:

Garage 1:

Revenue = (100 * 6) + (250 * 8) + (500 * 2) = 600 + 2000 + 1000 = 3600

Garage 2:

Revenue = (100 * 5) + (250 * 7) + (500 * 8) = 500 + 1750 + 4000 = 6250

Garage 3:

Revenue = (100 * 14) + (250 * 10) + (500 * 11) = 1400 + 2500 + 5500 = 9400

Garage 4:

Revenue = (100 * 11) + (250 * 13) + (500 * 5) = 1100 + 3250 + 2500 = 6850

Among these garages, the one that generates the maximum revenue is Garage 3 with a revenue of 9400.

So, the function should return 9400 as the maximum revenue generated by any of the garages in the input list.

Sample input

Sample Output

Instructions:

This is a template-based question; DO NOT write the "main" function.
Your code is judged by an automated system; do not write any additional welcome/greeting messages.
"Save and test" only checks for basic test cases; more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code in terms of both memory and execution time.

Solution

Approach:

We define a Garage struct to represent each garage's count of bikes, cars, and trucks.
The MaxRevenue function takes a vector of garages as input and calculates the revenue for each garage using the provided formula.
It keeps track of the maximum revenue found so far.
In the main function, we read the number of garages (m) and create a vector of garages with the specified counts for each type of vehicle.
We call the MaxRevenue function to find the maximum revenue among all the garages and then print the result.

Time Complexity: O(m)

Reading the input data (counts of vehicles for each garage) takes O(m) time, where 'm' is the number of garages.
The MaxRevenue function iterates through each garage once, performing constant-time calculations for each. Therefore, the loop's time complexity is O(m).
Finding the maximum revenue using max also takes O(m) time because we compare each garage's revenue.
Thus, the overall time complexity of the program is O(m).

Space Complexity: O(m)

The space complexity is determined by the memory used to store the vector of garages. Each garage occupies a constant amount of space (3 integers), and there are 'm' garages in total.
Therefore, the space complexity of the program is O(m) due to the storage of input data in the vector.
Other variables used in the program take constant space and do not contribute significantly to the space complexity.

Code:

#include <iostream>
#include <vector>

using namespace std;

struct Garage {
    int bikes;
    int cars;
    int trucks;
};

int MaxRevenue(vector<Garage>& garages, int m) {
    int maxRevenue = 0;

    for (const Garage& garage : garages) {
        int revenue = (100 * garage.bikes) + (250 * garage.cars) + (500 * garage.trucks);
        maxRevenue = max(maxRevenue, revenue);
    }

    return maxRevenue;
}

int main() {
    int m;
    cin >> m; // Number of garages

    vector<Garage> garages(m);

    for (int i = 0; i < m; i++) {
        cin >> garages[i].bikes >> garages[i].cars >> garages[i].trucks;
    }

    int result = MaxRevenue(garages, m);
    cout << result << endl;

    return 0;
}

15. Sum of Numbers

Problem Statement

You are required to implement the following function:

int SumPrimeIndices(int *arr, int n);

The function accepts an array 'arr' of 'n' integers as its argument. You are required to calculate the sum of numbers at prime indices in the array 'arr' and return the result.
Note:

1. If 'arr' is empty or null (in the case of Python), return -1.
2. 1 is not a prime number.
3. 0-based indexing is used in 'arr'.

Example:
Input:

Arr: 10 -12 2 5 3 15 17 21 -3 -4
N: 10

Output:

Explanation:

The numbers in 'arr' at prime indices are (2, 5, 15, 21), and their sum is 43, hence 43 is returned.

The custom input format for the above case:

10
10  -12  2  5  3  15  17  21  -3  -4

(The first line represents 'n', and the second line represents the elements of the array 'arr'.)

Sample input:

Arr:  -1  2  -3  55  51  34  5  -4  66  8  63  45
N: 12

Sample Output:

The custom input format for the above case:

12
-1  2  -3  55  51  34  5  -4  66  8  63  45

(The first line represents 'n', and the second line represents the elements of the array 'arr'.)

Explanation:
The numbers in 'arr' at prime indices are (-3, 55, 34, -4, 45), and their sum is 127, hence 127 is returned.

Instructions:

This is a template-based question; DO NOT write the "main" function.
Your code is judged by an automated system; do not write any additional welcome/greeting messages.
"Save and test" only checks for basic test cases; more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code in terms of both memory and execution time.

Solution

1. Intuition:
The code aims to find the sum of elements at prime indices in an array. It does so by iterating through the elements, checking if each index is prime, and if so, adding the element at that index to the sum.

2. Approach:
Here's how the code works step by step:

It starts by including the necessary libraries and namespaces (iostream and vector).
The SumPrimeIndices function takes two arguments: a vector of integers Arr and an integer n representing the number of elements in Arr.
It initializes an empty vector Arr2 to store prime indices.
If n is less than or equal to 1, it returns -1 as per the problem statement.
Otherwise, it enters a loop that iterates from 2 to n-1, checking for prime indices:
For each index i, it initializes a boolean variable is_prime as true.
Then, it enters another loop from 2 to i-1 to check for factors. If i is divisible by any number in this range, it sets is_prime to false and breaks out of the loop.
If is_prime is still true after the inner loop, it means i is prime, so it adds i to the Arr2 vector.
After finding all prime indices, it initializes a variable sum1 to store the sum of elements at prime indices.
It enters a loop to calculate the sum:
For each index i in Arr2, it adds Arr[i] to sum1.
Finally, it returns sum1.

In the main function:

It reads the input n.
It initializes a vector Arr of size n.
It reads the elements of the array Arr.
It calls the SumPrimeIndices function with Arr and n as arguments and prints the result.

3. Time Complexity:
The time complexity of this code is O(n^2) because it uses nested loops. The outer loop runs from 2 to n-1, and for each index i, the inner loop runs from 2 to i-1.

4. Space Complexity:
The space complexity is O(k), where k is the number of prime indices in the range [2, n-1]. In the worst case, all indices in this range are prime, so the space complexity is O(n).

Code

C++  code:
#include <iostream>
#include <vector>
using namespace std;

int SumPrimeIndices(vector<int> Arr, int n) {
    vector<int> Arr2;

    if (n <= 1) {
        return -1;
    } else {
        for (int i = 2; i < n; i++) {
            bool is_prime = true;
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                Arr2.push_back(i);
            }
        }
        int sum1 = 0;
        for (int i : Arr2) {
            sum1 += Arr[i];
        }
        return sum1;
    }
}

int main() {
    int n;cin >> n;
    vector<int> Arr(n);

    for (int i = 0; i < n; i++) {
        cin >> Arr[i];
    }

    cout << SumPrimeIndices(Arr, n) << endl;

    return 0;
}


Python code:


def SumPrimeIndices(Arr, n):
    Arr2 = []

    if n <= 1:
        return -1
    else:
        for i in range(2, n):
            is_prime = True
            for j in range(2, i):
                if i % j == 0:
                    is_prime = False
                    break
            if is_prime:
                Arr2.append(i)

        sum1 = 0
        for i in Arr2:
            sum1 += Arr[i]

        return sum1

def main():
    n = int(input())
    Arr = list(map(int, input().split()))

    result = SumPrimeIndices(Arr, n)
    print(result)

if __name__ == "__main__":
    main()

16. Decryt the string

Problem Statement
Implement the following function:

char* Decrypt(char str[], int n);

The function accepts a string 'str' of size 'n' as its argument. Implement the function to decrypt the given 'str' in such a way that each character of the string is replaced as follows:
('a' -> 'z', 'b' -> 'y', 'c' -> 'x', 'd' -> 'w', 'e' -> 'v', 'f' -> 'u', 'g' -> 't', 'h' -> 's', 'i' -> 'r', 'j' -> 'q', 'k' -> 'p', 'l' -> 'o', 'm' -> 'n', 'n' -> 'm', 'o' -> 'l', 'p' -> 'k', 'q' -> 'j', 'r' -> 'i', 's' -> 'h', 't' -> 'g', 'u' -> 'f', 'v' -> 'e', 'w' -> 'd', 'x' -> 'c', 'y' -> 'b', 'z' -> 'a').
Return the decrypted string.

Assumption:

The string contains only lowercase alphabets.

Note:

Return NULL if the string is null (or None in the case of Python).

Example:
Input:

Str: vmxibkgrlm

Output:

Encryption

Explanation:

The input string is decrypted as follows:

Str	          Decrypt
V	            e
M	            n
X	            c
I	            r
B	            y
K	            p
G	            t
R            	i
L	            o
M	            n

Thus, the output string is 'encryption'.

Custom Input Format for the above case:

10
vmxibkgrlm

Sample Input:

Str: xovzi

Sample Output:

Clear

Custom Input Format for the above case:

5
xovzi

Explanation:

The input string is decrypted as follows:

Str           Decrypt
X               C
o               l
v               e
z               a
i               r

Thus, the output string is 'clear'.

Instructions:

This is a template-based question; DO NOT write the "main" function.
Your code is judged by an automated system; do not write any additional welcome/greeting messages.
"Save and test" only checks for basic test cases; more rigorous cases will be used to judge your code while scoring.
Additional score will be given for writing optimized code in terms of both memory and execution time.

Solution

1. Intuition:
The code aims to decrypt a given string by replacing each character according to a specified pattern. To achieve this, it creates a mapping for character replacement and then iterates through the input string, updating each character based on the mapping.

2. Approach:

The code begins by creating a mapping for character replacement using an array called mapping. The mapping is constructed such that each character is replaced as follows: 'a' with 'z', 'b' with 'y', 'c' with 'x', and so on.
It then reads the length of the input string (n) and the input string (str) from the standard input.
Next, it checks if the input string is empty or NULL (when n is less than or equal to 0). If the input string is empty or NULL, it prints "NULL" and exits.
If the input string is valid, it proceeds to decrypt the string by iterating through each character.
During the iteration, it checks if the character is a lowercase letter ('a' to 'z'). If it is, it replaces the character with its corresponding decrypted character using the mapping array.
Finally, it prints the decrypted string to the standard output.

3. Time Complexity:

The time complexity of this code is O(n), where n is the length of the input string. This is because it iterates through the input string once, performing constant-time operations for each character.

4. Space Complexity:

The space complexity of this code is O(1) because it uses a fixed-size mapping array of size 26 to store the character replacements. The space required does not depend on the size of the input string, making it constant space.

Code

C++:
#include <iostream>
#include <cstring>

using namespace std;

char* Decrypt(char str[], int n) {
    // Create a mapping for character replacement
    char mapping[26];
    for (int i = 0; i < 26; i++) {
        mapping[i] = 'a' + 25 - i;
    }

    // Iterate through the input string and replace characters
    for (int i = 0; i < n; i++) {
        if (str[i] >= 'a' && str[i] <= 'z') {
            str[i] = mapping[str[i] - 'a'];
        }
    }

    return str;
}

int main() {
    int n;
    cin >> n;

    // Check if the input string is NULL
    if (n <= 0) {
        cout << "NULL" << endl;
        return 0;
    }

    char str[n];
    cin >> str;

    char* result = Decrypt(str, n);
    cout << result << endl;

    return 0;
}

IMPORTANT TIPS

- If you are trying to solve any one questions of above. Please! Give it a try first with your own . Well, it's quite easy level question. After that you can prefer this solution.
- There might be mistakes.Comment down and let me know , So that i can correct it.
- If Anyone want to see MCQ Question, I had attached a pdf file which contains some of question that has been asked.
  Check Here
- Please UpVote if this is Helpful one.

Comments (10)