Given an integer n, return the least number of perfect square numbers that sum to n.
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (t concatenated with itself 1 or more times)
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Input:
str1 = 'ABCABC', str2 = 'ABC'
Output:
'ABC'
Input:
str1 = "ABABAB", str2 = "ABAB"
Output:
'AB'
In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
Array of string is given ["abc, def, xyz, ..."]. You have to find the groups of related strings.
A String is related if the distance between each of the character of the string [at each index] is same.
Example
(d-a = 3 | e-b.= 3 | f-c=3) --> Hence abc and def are related.
Given an array of integers, find the longest subarray in this array which is divisible by k.
Example:
arr[] = 7 8 3 -3 4 2 1 and k = 3
The longest subarray is 7 8 3 -3 4 2 which is divisible by 3 so answer is 6
Given is an array of integers where each number exists exactly twice except one number.
It is also guaranteed that the duplicate occurrences occur consecutively.
Find the number that occurs only once
Example
1 1 2 2 4 4 6 8 8
Output:
6
We can solve the problem greedily by using two pointers technique as follows. Start from the first character and find its last occurrence in the string. Note that we have to include all the characters in between the first and the last occurrence of this character in the same partition. Now if the last occurrence of some of these characters lies further beyond, we have to extend the current partition upto that position. We keep scanning the characters and extending the partition until we reach the end of the partition. Now we have successfully created the first partition and can repeat the same process on the remaining string. This can be implemented using two pointers in a time complexity of O(N)
.
solve(s):
last = new Hashmap<char,int> //find the last occurrence of each character
for i from 1 to s.length():
last[s[i]] = i
ans = new int[]
i = 0
while(i < s.length()): //i marks the beginning of a new partition
target = last[s[i]] //first set the end of the partition as the last occurence of the i-th character
j = i
while(j < target): //now keep scanning the elements in between
target = max(target, last[s[j]]) //and extend the end of the partition as explained
j++
ans.append(j-i+1) //once we reach the end of the partition, append the length in ans
i = j+1 //set i to the start of the remaining string
return ans
We need to find the minimum number of perfect squares which sum up to the given number n. Here, we should first know Lagrange's four square theorem, which states that every natural number can be represented as the sum of 4 integer squares. So n = x^2 + y^2 + z^2 + w^2. Here, x, y, z, w can be any integer (possibly 0 as well). So our answer will always be less than or equal to 4.
Now, if the number n is a perfect square itself, then our answer will be 1. Otherwise, we check whether we can represent it as the sum of 2 perfect squares. So we need to check whether n = x^2 + y^2. We iterate overall all x from 1 to sqrt(n), and check whether n-x^2 is a perfect square or not. If we get a perfect square for some x, then the answer is 2.
Now, for numbers which neither have answer as 1 nor 2, we need to decide whether they can be represented as sum of 3 perfect squares or 4 perfect squares. For this we need to know Legendre's 3 square theorem, which states that every natural number can be represented as the sum of 3 perfect squares i.e. n = x^2 + y^2 + x^2 if and only if n is not of the form 4^a (8b+7) i.e. if n = 4^a (8b+7), it cannot be represented as the sum of 3 perfect squares.
Hence, we check this, and if n is of this form, then the answer is 4, (since 3 cannot be the answer), otherwise it is 3.
Question 3
Overview
prerequisite
Solution
Pseudo Code
int dfs(vector<vector<int>>& g, int i, int j) {
if (i < 0 || j < 0 || i >= g.size() || j >= g[i].size() || g[i][j] <= 0) return 0;
g[i][j] = -g[i][j];
auto res = max({ dfs(g, i + 1, j), dfs(g, i, j + 1), dfs(g, i - 1, j), dfs(g, i, j - 1) });
g[i][j] = -g[i][j];
return g[i][j] + res;
}
Question 6
Approach
Let's take an Example
In this example, the sum of subarray {2, 7, 6, 1} is 16 which when divided with k i.e. 3 gives 5 as quotient and 1 as remainder.
Pseudo Code
unordered_map<int, int> um;
int max_len = 0;
int curr_sum = 0;
for (int i = 0; i < n; i++)
{
curr_sum += arr[i];
int mod = ((curr_sum % k) + k) % k;
// if true then sum(0..i) is divisible by k
if (mod == 0)
max_len = i + 1;
else if (um.find(mod) == um.end())
um[mod] = i;
else
if (max_len < (i - um[mod]))
max_len = i - um[mod];
}
return max_len;
A naive solution to this problem is to check every consecutive element and determine the element that appears once in O(N)
. Another O(N)
solution (assuming that the input values are non negative) would be to just calculate the bitwise-XOR
of the given array. The elements appearing twice will cancel out and the odd element will be left out. But we can do better than O(N)
.
Better than O(N)
would be O(logN)
which implies, drumrolls 🥁 ..... Yeah you guessed it right --- Binary Search.
How to Binary search for the required index ?
Lets call the element to be found as the odd element. First note that the odd element will always be at even index if we consider 0-based indexing. This is because all the elements to the left of the odd element will be paired and hence there will be an even number of elements to its left. Hence we will binary search for only the even indexed positions.
How to determine if the odd element lies to the left or to the right of some index mid
?
Notice from the diagram that for all the even indexed positions to the left of the odd element, the value to the right is the same and for all the even indexed positions to the right (and including the odd element), the value to the right either does not exist or is different. Hence we can use this fact to determine if the odd element lies to the left or to the right of the current index mid
.
Thus, using these observations, we can binary search for the odd element and find it in a time complexity of O(logN)
and O(1)
space complexity.
solve(arr):
low = 0, high = (arr.size()-1)/2; //we only binary search for the even indexed positions, hence we only need n/2 search states
while(high > low):
mid = low + (high - low)/2;
index = 2*mid; //the real index in the array is determined by 2*mid
if(index+1 < nums.size() and nums[index+1] == nums[index]): //if the next index exists and the value is the same
//we are to the left of the required element and should move right, thus reduce search space to [mid+1,high]
low = mid+1;
else:
//we are either on the odd element or to its right, hence reduce our search space to [low,mid]
high = mid;
//finally low == high and we return the value at the actual index represented by the ans.
return nums[2*low];
Q2)
Analysis :
First observe that if string x is a divisor of string s then s=x+x...(concatenated some times) which means
sizeof(string s)=sizeof(string x) * (some positive integer) which means size of string x is a factor of size of string s.
Solution :
We could iterate over the common factors of string size of(s) and string size of(t) and find the common factor of both of them and then check whether a prefix of factor length is possible or not. For checking is it possible we could do it by taking a prefix of a factor length and check whether when it concatenates for length/factor times to give us a taken string and also check whether the chosen factor length prefix is common in both of them.
Pseudo Code
size_s=size of(s)
size_t=size of(t)
ans=0;
boolean possible(prefix_length)
{
x=prefix of s of prefix_length
y=prefix of t of prefix_length
x_concatenated=[x]*(size_s/prefix_length)
y_concatenated=[y]*(size_t/prefix_length)
if(x is equal to y and x_concatenated is equal to s and y_concatenated is equal to t)
return 1
else
return 0
}
iterate over common factors(f) of size_s and size_t
{
if(possible(f))
ans=max(ans,f);
}
return prefix of any string(either s or t) of ans length
Question No 7 Test cases are weird. Even the Brute Force is giving wrong answer on Test Case 2. Please check once.
***// int is long long int & vi is vector<int> int n; cin>>n; vi v(n); for (int i = 0; i < n; i++) { cin>>v[i]; } int x=0; for(int i=0; i
Hi Raunit, I have reviewed your code for the problem. Please notice the constraints on
a_i
in the problem on TJO. The values can also be negative and henceXOR
would result in absurd results. In the solution post, I had assumed thata_i
values would be non-negative, but I have prepared the problem considering the expected solution only. I have updated the solution post stating this.