survival8: Algorithms

Showing posts with label Algorithms. Show all posts

Sunday, June 15, 2025

Index of "Algorithms: Design and Analysis"

Toggle All Sections

From Codility

Course Link: By James Cutajar

From Hacker Earth

Track: Basic Programming > Input/Output > Basics of Input/Output

Super Easy

Discusson about Zoos (Super Easy Problem)
Track: Basic Programming > Input/Output > Basics of Input/Output
Discussion on Split houses (Super Easy Problem)
Track: Basic Programming > Input/Output > Basics of Input/Output

Easy

From ChatGPT

Difficulty: 3/10

Difficulty: 4/10

Discussion on "Longest Nice Substring" Problem

Monday, June 2, 2025

Discussion on 'Count Divisors' (Problem from Hacker Earth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem

You have been given 3 integers: l, r and k. Find how many numbers between l and r (both inclusive) are divisible by k. You do not need to print these numbers, you just have to find their count.

Input Format
The first and only line of input contains 3 space separated integers l, r and k.

Output Format
Print the required answer on a single line.

Constraints
1 <= l <= r <= 1000

1 <= k <= 1000

Sample Input
1 10 1
Sample Output
10

Time Limit: 1
Memory Limit: 256
Source Limit:

Psuedocode

if (r - l + 1) > k
    return (r - l + 1) / k
else:
    if floor(l / k) == floor(r / k):
        return 0
    else:
        return 1

Critique this psuedocode.

Solution


Your pseudocode is heading in the right direction by trying to find how many numbers in the range [l, r] are divisible by k, but it still contains logical issues. Let’s break it down carefully and critique each part:

Goal
We want to count all numbers x such that l ≤ x ≤ r and x % k == 0.

 Issues in Your Pseudocode
Your pseudocode:

if (r - l + 1) > k
    return (r - l + 1) / k
else:
    if floor(l / k) == floor(r / k):
        return 0
    else:
        return 1

Problem 1: (r - l + 1) / k doesn't count multiples of k
This gives the average number of elements between l and r per k steps, not how many elements are divisible by k.

Consider l = 3, r = 10, k = 2

r - l + 1 = 8

8 / 2 = 4 ✅ correct here by luck

But try l = 5, r = 15, k = 3:

r - l + 1 = 11, 11 / 3 = 3 ❌ wrong (actual count: 4 → 6, 9, 12, 15)

🔴 Problem 2: Your else block logic is oversimplified
plaintext
Copy
Edit
if floor(l / k) == floor(r / k):
    return 0
else:
    return 1
This assumes that at most one number divisible by k exists in [l, r], which is incorrect.

For example, l = 3, r = 10, k = 2:

floor(3/2) = 1, floor(10/2) = 5 → not equal → returns 1 ❌ but actual count is 4

✅ Correct and Simple Pseudocode

Input: l, r, k

# Use integer division (i.e., floor)
count = floor(r / k) - floor((l - 1) / k)

Return count
✅ Why this Works
Let’s take l = 5, r = 15, k = 3

Numbers ≤ 15 divisible by 3: 3, 6, 9, 12, 15 → total = floor(15/3) = 5

Numbers ≤ 4 divisible by 3: 3 → total = floor(4/3) = 1

So numbers divisible by 3 in [5, 15] = 5 - 1 = 4

💡 Final Thoughts
❌ Avoid using (r - l + 1) / k unless l = 1 and k = 1

✅ Stick to the formula floor(r / k) - floor((l - 1) / k) for correct results in all ranges

Would you like a Python function implementing this pseudocode too?
    
Explanation

✅ Correct Way to Count Multiples of k in [l, r]
The correct formula is:

count = floor(r / k) - floor((l - 1) / k)
It works because:

floor(r / k) counts how many numbers from 1 to r are divisible by k

floor((l - 1) / k) counts how many from 1 to l-1 are divisible by k

Subtracting the two gives how many are in the range [l, r]

Discussion on 'Palindromic Strings' (Problem from Hacker Earth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem
You have been given a String S. You need to find and print whether this string is a palindrome or not. If yes, print "YES" (without quotes), else print "NO" (without quotes).

Input Format
The first and only line of input contains the String S. The String shall consist of lowercase English alphabets only.

Output Format
Print the required answer on a single line.

Constraints 
1 <= len(S) <= 100

Note
String S consists of lowercase English Alphabets only.

Sample Input
aba
Sample Output
YES
Time Limit: 1
Memory Limit: 256
Source Limit:

Psuedo Code

I would propose two approaches to handling this:

Approach 1

Using indexing [::-1] to reverse the string and checking if matches the original string.

Approach 2

Using recursion. It is based on the fact that a string S of length N would be palindrome then all the substrings S[1:N-1], S[2:N-2],...,S[X, N-X] would also be palindrome. The idea for code would be (to take out first and last characters of the string and check if the resultant substring is a palindrome) and do these two thing recursively.

Critique this psuedo code.

Your proposed pseudocode outlines two solid approaches to checking whether a string is a palindrome. Here's a critique and comparison of both:

✅ Approach 1: Reverse and Compare

Pseudocode Summary:

Reverse the string.
Compare it with the original.
If equal → "YES", else → "NO".

✅ Pros:

Simple & clean: Very readable and requires only a single line in most programming languages.
Efficient: Time complexity is O(N) and no unnecessary recursion or iteration beyond what's required.
Best for constraints: Since len(S) ≤ 100, this is highly optimal and safe to use.

❌ Cons:

Memory usage: Creates a reversed copy of the string, so uses O(N) extra space.

Verdict:

Best option for this problem due to simplicity and efficiency.

✅ Approach 2: Recursive Check

Pseudocode Summary:

If first and last characters are equal, recursively check the substring in between.
Base case: If the string length is 0 or 1 → return "YES".

✅ Pros:

Demonstrates deeper thinking: Good for interviews or showing understanding of recursion.
Elegant: Reflects the recursive structure of the palindrome definition.

❌ Cons:

Less efficient: Recursive calls add function call overhead.
Stack overflow risk: For larger inputs (though len ≤ 100 is safe here).
Overkill: Too much machinery for a very simple check.

Verdict:

Nice to know for academic interest, but not preferred in real-world scenarios unless recursion is specifically required.

✅ Final Suggestion

If you’re writing production code or competitive programming solutions: Go with Approach 1.

If you're preparing for interviews and want to impress with recursion skills: Show Approach 2 as a follow-up, but note that it's not the most optimal.

Would you like both approaches written in actual code for comparison?

Yes, please share a more optimal solution.

Sure! Here's a more optimal (and standard) solution to check if a string is a palindrome — using the reverse-and-compare method, which is both simple and efficient.

✅ Optimal Solution (Reverse and Compare)

python
S = input().strip()

if S == S[::-1]:
    print("YES")
else:
    print("NO")

🔍 Explanation:

S[::-1] creates a reversed version of the string.
If the original and reversed strings are the same, it's a palindrome.
Time complexity: O(N)
Space complexity: O(N) (due to the reversed copy)

✅ Alternative: Two-Pointer Approach (Saves Memory)

If you want O(1) space, you can avoid reversing the string:

python
S = input().strip()
is_palindrome = True

for i in range(len(S) // 2):
    if S[i] != S[-(i + 1)]:
        is_palindrome = False
        break

print("YES" if is_palindrome else "NO")

🔍 Why This is More Optimal:

Uses only a flag and a loop.
No reversed copy of the string.
Time complexity: O(N), Space complexity: O(1)

This version is better if memory is a concern or you want to show detailed logic (e.g. in interviews).

Let me know if you'd like to see the recursive version too!

Discussion on 'Toggle String' (Problem from HackerEarth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem
You have been given a String S consisting of uppercase and lowercase English alphabets. You need to change the case of each alphabet in this String. That is, all the uppercase letters should be converted to lowercase and all the lowercase letters should be converted to uppercase. You need to then print the resultant String to output.

Input Format
The first and only line of input contains the String S

Output Format
Print the resultant String on a single line.

Constraints
1 <= length(S) <= 100 

Sample Input
abcdE
Sample Output
ABCDe

Psuedo code

t = ""
for i in S:
    if i.isupper():
        t += i.lower()
    else:
        t += i.upper()

Critique this psuedo code.

Critique by ChatGPT

Your pseudocode is clear, correct, and solves the problem as intended — it swaps the case of each letter in the string. Here's a detailed critique of its strengths and a few potential improvements:

✅ Strengths

Correct Logic:
- It checks each character: if it’s uppercase, it converts to lowercase, and vice versa.
- This aligns exactly with the problem requirements.
Readable and Intuitive:
- Simple variable names like t and i, and clear conditionals make the code easy to follow.
Character-wise Traversal:
- Traversing each character individually ensures all characters are handled properly.

⚠️ Possible Improvements

Performance Consideration (String Concatenation in Loop)
- Strings in Python are immutable, so doing t += i.upper() repeatedly creates a new string at every step, which can be inefficient in longer strings.
- Better Approach: Use a list to build characters, then join:
```
python
result = []
for i in S:
    if i.isupper():
        result.append(i.lower())
    else:
        result.append(i.upper())
t = ''.join(result)
```
Better Variable Naming
- t and i are fine for pseudocode, but in actual code, consider using:
  - char instead of i
  - result instead of t
- Improves readability, especially for beginners or interviews.
Alternative Built-in Method
- Python has a built-in method: str.swapcase() which does exactly this. For real-world use:
```
python
print(S.swapcase())
```
- However, since you're showing your logic manually (perhaps for an interview or educational context), it's good to write it out.

✅ Verdict:

Your pseudocode is functionally correct and clear, but could be slightly optimized for performance and readability in actual implementation. Great job!

Discussion About 'Find Product' (Problem from HackerEarth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem
You have been given an array A of size N consisting of positive integers. You need to find and print the product of all the number in this array Modulo 
10^9+7.

Input Format:
The first line contains a single integer N denoting the size of the array. The next line contains N space separated integers denoting the elements of the array

Output Format:
Print a single integer denoting the product of all the elements of the array Modulo 10^9 + 7.

Constraints:


Sample Input
5
1 2 3 4 5
Sample Output
120
Time Limit: 1
Memory Limit: 256
Source Limit:

Explanation
There are 5 integers to multiply. Let's store the final answer in answer variable. Since 1 is identity value for multiplication, initialize 
answer as 1.

So the process goes as follows:

answer = 1
answer = (answer * 1) % (10^9 + 7)
answer = (answer * 2) % (10^9 + 7)
answer = (answer * 3) % (10^9 + 7)
answer = (answer * 4) % (10^9 + 7)
answer = (answer * 5) % (10^9 + 7) 

The above process will yield answer as 120.

Can you give psuedo code for this?

Here is the pseudocode for the problem that calculates the product of an array modulo $10^9 + 7$ :

✅ Pseudocode

mathematica
1. Read integer N  // size of array

2. Read array A of N space-separated integers

3. Set MOD = 10^9 + 7

4. Initialize answer = 1

5. For each element x in A:
       answer = (answer * x) % MOD

6. Print answer

💡 Explanation

Step 1–2: Read input values.
Step 3: Define the modulo value as $10^9 + 7$ , a common modulus to avoid integer overflow.
Step 4: Start with answer = 1, since 1 is the identity for multiplication.
Step 5: Loop through each number and multiply it to answer, taking modulo after each multiplication to keep numbers manageable.
Step 6: Output the final result.

This pseudocode is efficient and handles the problem within the constraints. You can now convert it easily into any programming language like Python, C++, or Java. Let me know if you'd like code in a specific language!

Discussion about 'Ali and Helping innocent people' (Problem from HackerEarth)

To See All Articles About Technology: Index of Lessons in Technology

Try it out

Problem

Arpasland has surrounded by attackers. A truck enters the city. The driver claims the load is food and medicine from Iranians. Ali is one of the soldiers in Arpasland. He doubts about the truck, maybe it's from the siege. He knows that a tag is valid if the sum of every two consecutive digits of it is even and its letter is not a vowel. Determine if the tag of the truck is valid or not.

We consider the letters "A","E","I","O","U","Y" to be vowels for this problem.

Input Format

The first line contains a string of length 9. The format is "DDXDDD-DD", where D stands for a digit (non zero) and X is an uppercase english letter.

Output Format

Print "valid" (without quotes) if the tag is valid, print "invalid" otherwise (without quotes)

Sample Input
12X345-67
Sample Output
invalid
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
The tag is invalid because the sum of first and second digit of it is odd (also the sum of 4'th and 5'th, 5'th and 6'th and 8'th and 9'th are odd).

Psuedo-code

There are two ways I can think of for solving this problem.

Way 1

1. Assuming that the format of tag does not change over time. To determine if a tag is valid or not, I would take following steps:

2. I would check if tag[2] is a vowel or not. If it's a vowel: return invalid.

3. I would sum up tag[0]+tag[1] and check if it is even. If it's odd: return invalid.

4. I would sum up tag[4]+tag[5] and check if it is even. If it's odd: return invalid.

5. I would sum up tag[5]+tag[6] and check if it is even. If it's odd: return invalid.

6. I would sum up tag[8]+tag[9] and check if it is even. If it's odd: return invalid.

7. Return valid.

Way 2

1. Assuming that the format of tag does change over time with only allowed characters as A-Z, 1-9 and "-". To determine if a tag is valid or not, I would take the following steps:

2. I would loop over all the characters of the tag.

3. Initialize a variable last_char as "NA".

3. For first character: if it's a number: store it in last_char. Else if is a alphabet: check if is a vowel, if it's vowel then return invalid.

4. Second character onwards: if it's a number and last_char is also a number: sum up the number and last_char. If the sum is odd, return invalid.
Else if it's alphabet: check if is a vowel, if it's vowel then return invalid.

5. Return valid.

Compare and contrast two approaches and critique both.

Critique by ChatGPT

Great job outlining two viable approaches to this problem! Both are valid and solve the problem in different ways. Let’s break them down one by one, compare them, and identify pros and cons to help you decide which is better in different situations.

✅ Restating the Problem Requirements

Given a string like "12X345-67", you must:

Check if the letter in position 2 is not a vowel.
Check if the sum of specific consecutive digit pairs is even:
- tag[0] + tag[1]
- tag[3] + tag[4]
- tag[4] + tag[5]
- tag[7] + tag[8]

Now let's evaluate both your approaches.

✅ Way 1: Index-based validation (Fixed Format)

🔍 Steps Recap:

Check tag[2] is not a vowel.
Validate digit pairs: [0+1], [3+4], [4+5], [7+8]
Return invalid if any check fails.

✅ Pros:

Highly efficient (constant time, O(1)) — only 4 fixed checks.
Simple and readable if the format is guaranteed.
Minimal computation — avoids unnecessary looping.

❌ Cons:

Rigid: Completely breaks if the format changes.
- e.g., if the position of digits or letters changes, or new rules are added.
Not easily reusable for other patterns.

🔎 Best use-case:

When the format is strictly fixed — great for tightly scoped system checks like license plate formats or barcode rules.

✅ Way 2: Character-based validation (Dynamic Format)

🔍 Steps Recap:

Loop over the string.
Track the last digit seen.
For each character:
- If alphabet → check if vowel.
- If digit:
  - If previous was also digit → check if sum is even.

✅ Pros:

Flexible: Works even if the format evolves or changes.
Scalable: Easier to extend or modify (e.g., different lengths or more rules).
Robust: Does not rely on exact positions.

❌ Cons:

Less performant: O(n), though still fast for small input (n=9).
Slightly more complex logic-wise than hardcoded index checks.
Might validate unintended patterns if not carefully handled (e.g., two digits from separate segments).

🔎 Best use-case:

When the input format can vary, or the rules are expected to change or be reused in other contexts.

⚖️ Comparison Summary Table

Criteria	Way 1 (Fixed Format)	Way 2 (Flexible Format)
Performance	✅ Faster (O(1))	❌ Slower (O(n))
Flexibility	❌ Not flexible	✅ Highly flexible
Readability	✅ Easier to follow	⚠ Slightly more complex
Robustness	❌ Fragile to format change	✅ Handles varied inputs
Scalability	❌ Hard to extend	✅ Easy to generalize
Best for	Fixed formats	Variable formats

🏁 Conclusion

Use Way 1 if you're working in a controlled environment with fixed format tags (like this specific problem).
Use Way 2 if you want your code to be robust, extensible, or you’re designing for systems where formats may change (e.g., real-world parsers or validators).

If this were an interview, I'd recommend starting with Way 1 for efficiency and then explaining that Way 2 could be used in production systems for robustness.

Let me know if you'd like implementations of both approaches for comparison.

How would you solve it?

To solve the "Truck Tag Validator" problem, I would choose Way 1 (fixed index-based approach) because:

The format "DDXDDD-DD" is fixed (length is always 9).
Index-based validation is clean, fast, and easy to reason about for such problems.

✅ Key Validation Rules (based on fixed positions)

Given the string: tag = "DDXDDD-DD", check:

The character at index 2 must not be a vowel: 'A', 'E', 'I', 'O', 'U', 'Y'
The sum of digits at positions:
- 0 + 1 must be even
- 3 + 4 must be even
- 4 + 5 must be even
- 7 + 8 must be even

✅ Python Solution:

python
def is_valid_tag(tag):
    vowels = {'A', 'E', 'I', 'O', 'U', 'Y'}

    # Check the letter is not a vowel
    if tag[2] in vowels:
        return "invalid"

    # Helper to check if sum of two digit characters is even
    def is_even_sum(i, j):
        return (int(tag[i]) + int(tag[j])) % 2 == 0

    if not is_even_sum(0, 1):
        return "invalid"
    if not is_even_sum(3, 4):
        return "invalid"
    if not is_even_sum(4, 5):
        return "invalid"
    if not is_even_sum(7, 8):
        return "invalid"

    return "valid"

# Sample Inputs
print(is_valid_tag("12X345-67"))  # ➞ invalid
print(is_valid_tag("24B468-80"))  # ➞ valid (if B is not a vowel and sums are all even)

🧪 Sample Run:

For input: "12X345-67"

tag[2] = X → Not a vowel ✅
1+2 = 3 → Odd ❌ → Return "invalid"

⚙️ Time & Space Complexity

Time: O(1) → constant number of checks
Space: O(1) → uses only a few variables

Let me know if you'd like the flexible (Way 2) version too or want to make it more generic.