[HackerRank] Check Palindrome by Filtering Non-Letters

Check Palindrome by Filtering Non-Letters

Difficulty: Easy

Given a string containing letters, digits, and symbols, determine if it reads the same forwards and backwards when considering only alphabetic characters (case-insensitive).

Example

Input

code = A1b2B!a

Output

1

Explanation

- Step 1: Extract only letters → ['A','b','B','a'] 
- Step 2: Convert to lowercase → ['a','b','b','a'] 
- Step 3: Compare sequence forward and backward: 'abba' == 'abba' → true

Input Format

• A string code containing letters (A–Z, a–z), digits (0–9), and symbols

Constraints

• 0 <= code.length <= 1000
• For all 0 <= i < code.length: 33 <= ASCII(code[i]) <= 126
• code contains only printable ASCII characters (letters, digits, symbols)

Output Format

• Return a boolean value: 1 if true & 0 if false.

Sample Input 0

Z

Sample Output 0

1

Sample Input 1

abc123cba

Sample Output 1

1 

Consideration:

1. Two Pointers: Left index, Right index to compare the alphabetic characters.

2. If not alphabetic characters, jump to the next index. (Left Index ++, Right Index --)

3. case insensitive: compare the distance with 'A' or 'a'.

Code:

/*

 * Complete the 'isAlphabeticPalindrome' function below.

 *

 * The function is expected to return a BOOLEAN.

 * The function accepts STRING code as parameter.

 */

bool isAlphabeticPalindrome(string code) {

    int n = code.size();

    //cout << "n = " << n << "\n";

    int i = 0, j = n-1;

    if (n==0 || n==1) return 1;

   

    while (i<j) {

        //cout << "i = " << i << "\n";

        //cout << "j = " << j << "\n";

        if (((code[i]>='A') && (code[i] <= 'Z')) || ((code[i] >= 'a') && (code[i] <= 'z'))) {          

            if (((code[j]>='A') && (code[j] <= 'Z')) || ((code[j] >= 'a') && (code[j] <= 'z'))) {

                if (code[i]==code[j]) {

                    i++;

                    j--;

                }

                else if (code[i]>code[j]) {

                    if (code[i]>='a') {

                        if ((code[j]-'A')==(code[i]-'a')){

                            i++;

                            j--;

                        }

                        else {

                            //cout << "i = " << i << "[" << code[i] << "]" << "\n";

                            //cout << "j = " << j << "[" << code[j] << "]" << "\n";  

                            return 0;

                        }

                    }

                    else {

                        //cout << "i = " << i << "[" << code[i] << "]" << "\n";

                        //cout << "j = " << j << "[" << code[j] << "]"<< "\n";

                        return 0;

                    }

                }

                else if (code[i]<code[j]) {

                    if (code[j]>='a') {

                        if ((code[i]-'A')==(code[j]-'a')){

                            i++;

                            j--;

                        }

                        else {

                            //cout << "i = " << i << "[" << code[i] << "]" << "\n";

                            //cout << "j = " << j << "[" << code[j] << "]" << "\n";                            

                            return 0;

                        }

                    }

                    else {

                        //cout << "i = " << i << "[" << code[i] << "]"<< "\n";

                        //cout << "j = " << j << "[" << code[j] << "]"<< "\n";

                        return 0;

                    }                    

                }

            }

            else j--;

        }

        else i++;

    }

    return 1;

}

[HackerRank] Longest Arithmetic Subsequence with Given Difference

 

Longest Arithmetic Subsequence with Given Difference

Difficulty: Hard.

Given an array of integers and a positive integer k, find the length of the longest arithmetic progression with common difference k. Ignore duplicates.

Example

Input

arr = [8, 1, -1, 0, 3, 6, 2, 4, 5, 7, 9]
k = 2

Output

6

Explanation

Remove duplicates (none here) and consider the set of unique elements: 

We seek the longest arithmetic progression with difference k=2. 

Starting at -1 gives the sequence [-1,1,3,5,7,9] of length 6. 
No other starting point yields a longer progression, so the result is 6.

Input Format

• The first line contains an integer n denoting the number of elements in the array.
• The next n lines contains an integer denoting elements in the array.
• The last line contains the value for integer k.

Example

11 → number of elements
8 → elements of the array
1
-1
0
3
6
2
4
5
7
9
2 → value of k

Constraints

• 0 <= arr.length <= 100000
• -10^9 <= arr[i] <= 10^9 for each 0 <= i < arr.length
• 1 <= k <= 10^9
• Duplicates may appear in arr but should be ignored when forming the progression

Output Format

• A single integer denoting the length of the longest arithmetic progression.

Sample Input 0

0
5

Sample Output 0

0

Sample Input 1

1
42
7

Sample Output 1

1

Consideration:

1. Sort the vector.

2. Each element could be selected to be start element.

3. While searching for the next same difference value, you could break the loop if the difference with current value is larger than k.

4. Skip next element searching if that difference with current element equals to k. (Already calculated.)

5. Very important: If don't apply this point, it may become timeout for test case#13.

    When the rest number of the vector is smaller than longest length of same k-difference sequence we had found, just skip the rest check. It's because no chance to get another longer length for next search.

Code:

/*

 * Complete the 'findLongestArithmeticProgression' function below.

 *

 * The function is expected to return an INTEGER.

 * The function accepts following parameters:

 *  1. INTEGER_ARRAY arr

 *  2. INTEGER k

 */

int findLongestArithmeticProgression(vector<int> arr, int k) {

    sort(arr.begin(), arr.end());

    int longest_length=1;

    int cur_length;

    int n = arr.size();

    if (n==0) return 0;

    if (n==1) return 1;

    int pv;

    for (int i=0;i<n-longest_length;i++) {

        cur_length=1;

        pv = arr[i];

       

        if ( (i>0) && ((arr[i]-arr[i-1])==k) ) continue;

        for (int j=i+1;j<n;j++) {

            if ((arr[j]-pv)==k) {

                //cout << "pv = " << pv << "\n";

                //cout << "cv = " << arr[j] << "\n";

                //cout << "j = " << j << "\n";

                cur_length++;

                //cout << "cur_length = " << cur_length << "\n";

                pv = arr[j];

            }

            else if (((arr[j]-pv) > k)) {

                break;

            }

        }

        if (cur_length > longest_length) {

            longest_length = cur_length;

        }

    }

    return longest_length;

}

[HankerRank] Find the Smallest Missing Positive Integer

Find the Smallest Missing Positive Integer

Difficulty: Easy

Given an unsorted array of integers, find the smallest positive integer not present in the array in O(n) time and O(1) extra space.

Example

Input

orderNumbers = [3, 4, -1, 1]

Output

2

Explanation

We want the smallest positive missing integer.

Start with [3, 4, -1, 1]
- i=0: value 3 ⇒ swap with index 2 ⇒ [-1, 4, 3, 1]
- i=0: value -1 is out of range ⇒ move on
- i=1: value 4 ⇒ swap with index 3 ⇒ [-1, 1, 3, 4]
- i=1: value 1 ⇒ swap with index 0 ⇒ [1, -1, 3, 4]
- now 1 at index 0, 3 at 2, 4 at 3; -1 remains at index 1

Scan from index 0:
index 0 has 1 (correct), index 1 has -1 (not 2) ⇒ missing positive is 2

Input Format

• An integer n on the first line, where 0 ≤ n ≤ 1000.
• The next n lines contains an integer representing orderNumbers[i].

Example

4
3
4
-1
1

here 4 is the length of array, followed by the elements of array on each line.

Constraints

• 0 <= orderNumbers.length <= 1000
• -10^9 <= orderNumbers[i] <= 10^9 for all 0 <= i < orderNumbers.length
• Duplicates are allowed in orderNumbers
• Negative numbers and zero are allowed in orderNumbers

Output Format

• A single integer denoting the smallest positive order number (≥1) that does not appear in the input array.

Sample Input 0

0

Sample Output 0

1

Sample Input 1

1
1

Sample Output 1

2

Consideration:
1. Sort the vector first.

2. positive value starting from 1. If found, increase the value and check next element. If not found, current value is the result.

Code:

/*

 * Complete the 'findSmallestMissingPositive' function below.

 *

 * The function is expected to return an INTEGER.

 * The function accepts INTEGER_ARRAY orderNumbers as parameter.

 */

int findSmallestMissingPositive(vector<int> orderNumbers) {

    sort(orderNumbers.begin(), orderNumbers.end());

    int n = orderNumbers.size();

    int minPv=1;

    for (int i=0;i<n;i++) {

        if (orderNumbers[i] > minPv) return minPv;

        if (orderNumbers[i] == minPv) {

            minPv++;

        }

    }

    return minPv;

}