Problem-1 Zlatan and Tricks Solution

Topics - : 

• Array Mathematics

• Combinatorics / Counting

Overview

The total sum of the entire array is exactly m. To form a subsequence with a sum of m - 1, the elements we leave out must sum to exactly 1. Therefore, the number of such subsequences is simply the total count of the number 1 present in the initial array.

Approach

1. The Logic Behind the Sum

This is a clever logic puzzle! Instead of building every possible combination to see what works, we just look at what we are leaving behind. If the total array sums up to m, and we want a piece of it that sums to m - 1, the piece we remove must be exactly 1.

2. Counting the Targets

Since we just need to drop a single 1 to get our desired sum, every individual 1 in the array represents a valid, unique way to form the subsequence. We just iterate through the array and count how many times the number 1 appears.

Code Implementation

function countSubsequences(n, array):
    countOfOnes = 0
    
    for i from 0 to n - 1:
        if array[i] == 1:
            countOfOnes = countOfOnes + 1
            
    return countOfOnes

Problem-2 Professor Plays a Game Solution

Topics Involved / Prerequisites

• Array Sorting

• Greedy Approach

Overview

1. Sorting the array allows us to easily access the largest positive and smallest negative numbers.
2. The maximum product of three numbers usually comes from the three largest positive numbers at the end.
3. However, multiplying the two smallest negative numbers yields a large positive number, which must be checked against the largest element.

Approach

1. Sorting the Board This is a classic optimization challenge! When dealing with maximum products, we always want the absolute highest values. By sorting the array in ascending order, we push the largest positive numbers to the far right, and the largest negative numbers (smallest values) to the far left.

2. Comparing the Two Extremes There are only two ways to get the maximum product of three numbers:

• Multiply the three largest numbers together: array[n-1] * array[n-2] * array[n-3]

• Multiply the two smallest negative numbers (which makes a positive) by the absolute largest number: array[0] * array[1] * array[n-1] We calculate both and simply return whichever is bigger!

Code Implementation

function maxProductOfThree(n, array):
    sort(array)
    

    opt1 = array[n-1] * array[n-2] * array[n-3]
    opt2 = array[0] * array[1] * array[n-1]
    
    return max(opt1, opt2)

Forgotten Number Solution

Topics -:

• Mathematical

Overview

The expected sum if every number from 1 to n is added exactly twice is simply n *(n + 1). By subtracting the actual given sum S from this perfect expected total, we get the total value that is missing. Since the logic implies the missing number was omitted completely (missed twice), we divide this difference by 2.

Approach

1. Finding the Perfect Sum

This is a fun mathematical trick! Rather than simulating the friend's exact additions, we use the classic sum formula. The sum of 1 to n is n* (n + 1) / 2. Since he was supposed to add them twice, the expected sum is just n*(n + 1).

2. Finding the Difference

We subtract the friend's actual sum S from our perfect expected sum. The problem's example output shows that the missing number was skipped both times. So, the difference we calculated is actually twice the value of the forgotten number. We just divide the difference by 2 to get our final answer!

function findForgottenNumber(n, S):

    expectedSum = n * (n + 1)

    difference = expectedSum - S
    
    return difference / 2

Time Complexity

• Time: O(1) - The entire calculation is done using a direct mathematical formula.

• Space: O(1) - No extra memory is used.

Problem-4 King Solution

Topics-: Array

Overview

A king must have more kindness than everyone else, meaning we are looking for the absolute maximum values in the entire array. We first scan the array to determine this highest possible kindness score among all people. Then, we scan again to find the positions of this maximum score, ensuring they are strictly greater than their immediate left and right neighbors.

Approach

Approach

1. Finding the Highest Standard This requires a two-step validation! To be a true king, you must first have more kindness than the general population. This means the king can only be someone who shares the maximum value found in the entire array.

2. Checking the Neighbors Once we know what the maximum value is, we loop through the array again. If we find someone with that maximum value, we check the person to their immediate left and right. If they are strictly greater than both neighbors (handling the edges carefully), we print their 1-based index.

Psudo Code 

function findKings(n, kind):
    maxKindness = -1
    
    // Step 1: Find the absolute maximum
    for i from 0 to n - 1:
        maxKindness = max(maxKindness, kind[i])
        
    // Step 2: Validate the neighbors
    for i from 0 to n - 1:
        if kind[i] == maxKindness:
            greaterThanLeft = (i == 0) OR (kind[i] > kind[i-1])
            greaterThanRight = (i == n - 1) OR (kind[i] > kind[i+1])
            
            if greaterThanLeft AND greaterThanRight:
                print(i + 1 + " ") 

Problem5 Class Test 1 Solution

Topics 

• Hash Sets

Overview

1. To find unique scores while maintaining their original order, we need to filter out any duplicates as we read the list.
2. We can use a hash set to keep track of which scores we have already encountered and printed to the screen.
3. Finally, the total size of this hash set will give us the exact number of unique scores to print at the end.

Approach

1. Filtering in Real-Time This is a straightforward data filtering task! The key is to maintain the original sequence. As we loop through the test scores, we check if the current score is already in our Hash Set.

2. Storing and Printing If the score is not in the set, it's a brand new unique score! We print it out immediately, and then add it to our set so we don't print it again later. Once the loop finishes, the length of our set is the total number of unique scores.

Code Implementation-: 

function processScores(n, array):
    create an empty Hash Set 'seen'
    
    // Print unique elements in order
    for i from 0 to n - 1:
        if array[i] is NOT in seen:
            print(array[i] + " ")
            seen.insert(array[i])
            
    print new line
    
    // Print total count
    print("The number of unique scores are " + seen.size())

Time Complexity

• Time: O(N) - We iterate through the array once to find the subarray, and at most once more to find the min/max inside it.

• Space: O(N) - In the worst case, we store N distinct prefix sums in the hash map.