0 like 0 dislike
1,212 views
| 1,212 views

0 like 0 dislike

Q1. Break Palindrome

Given a palindrome, you must change 1 character in it such that the string is not a palindrome and is lexicographically smallest.
Output the string if you are able to do so, otherwise return "IMPOSSIBLE"

Sampe Testcase:

• "aaabbaaa" -> "aaaabaaa"
• "aa" -> "IMPOSSIBLE"

Constraint:

• `1 <= N <= 1000`
• `the palindrome consists of only lowercase English letter`

Q2. Pairs of Songs

Given a list of songs's durations `songs[]`, such as `[30, 60, 180]`, we have to find the number of pairs `(i, j)` where `j > i` such that `songs[i] + songs[j]` is a multiple of 60.

Constraint

• `1 <= N <= 100000`
• `1 <= song[i] <= 1000`

by Expert (46,090 points)
0 like 0 dislike

Q1) Optimized :-

``````// Time Complexity :- O(N)

// Space Complexity :- O(1)

string helper(string str)
{
int n = str.size();

for(int i = 0; i < n / 2; i++)
{
if(str[i] != 'a')
{
str[i] = 'a';

return str;
}
}

return "IMPOSSIBLE";
}

int main()
{
cout<<helper("aaabbaaa") << endl;

cout<<helper("aa") << endl;

return 0;
}``````

Q2) Using Hashmap :-

``````// Time Complexity :- O(N)

// Space Complexity :- O(N)

int helper(vector<int> arr)
{
int n = arr.size();

int count = 0;

unordered_map<int, int> mp;

for(int i = 0; i < n; i++)
{
int rem = arr[i] % 60;

int need = 0;

if(rem != 0)
{
need = 60 - rem;
}

count += mp[need];

mp[rem]++;
}

return count;
}

int main()
{
cout << helper({30, 60, 180, 30, 1, 90}) << endl;

return 0;
}``````

by Expert (46,090 points)