1.
Flood fill Algorithm
Given a 2D screen, location of a pixel in the screen ie(x,y) and a color(K), your task is
to replace color of the given pixel and all adjacent(excluding diagonally adjacent)
same colored pixels with the given color K.
Example:
{{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 2, 2, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 0, 1, 0},
{1, 1, 1, 2, 2, 2, 2, 0},
{1, 1, 1, 1, 1, 2, 1, 1},
{1, 1, 1, 1, 1, 2, 2, 1},
};
x=4, y=4, color=3
{{1, 1, 1, 1, 1, 1, 1, 1},
{1, 1, 1, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 1},
{1, 3, 3, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 0, 1, 0},
{1, 1, 1, 3, 3, 3, 3, 0},
{1, 1, 1, 1, 1, 3, 1, 1},
{1, 1, 1, 1, 1, 3, 3, 1}, };
Note: Use zero based indexing.
Input:
The first line of input contains an integer T denoting the no of test cases. Then T test
cases follow. The first line of each test case contains Two integers N and M denoting
the size of the matrix. Then in the next line are N*M space separated values of the
matrix. Then in the next line are three values x, y and K.
Output:
For each test case print the space separated values of the new matrix.
Constraints:
1 <= T <= 100
1 <= M[][] <= 100
Example:
Input:
3
34
011011110123
015
22
1111
018
44
1234123412341324
029
Output:
055055550523
8888
1294129412941324
CODE:
using namespace std;
void paint(int n,int m,int arr[100][100],int x,int y,int prevc,int newc)
if(x>=n || y>=m || x<0 || y<0)
return;
if(arr[x][y]==newc)
return;
if(arr[x][y]!=prevc)
return;
arr[x][y]=newc;
paint(n,m,arr,x+1,y,prevc,newc);
paint(n,m,arr,x-1,y,prevc,newc);
paint(n,m,arr,x,y+1,prevc,newc);
paint(n,m,arr,x,y-1,prevc,newc);
return;
int main()
int t;
cin>>t;
while(t--)
int n,m;
cin>>n>>m;
int arr[100][100];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>arr[i][j];
int x,y,k;
cin>>x>>y>>k;
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<m;j++)
// cout<<arr[i][j]<<" ";
// cout<<endl;
// }
// cout<<"------------------------------------------------"<<endl;
int prevc=arr[x][y];
int newc=k;
paint(n,m,arr,x,y,prevc,newc);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
return 0;
2. Number of paths
The problem is to count all the possible paths from top left to bottom right of
a MxN matrix with the constraints that from each cell you can either move
to right or down.
Input:
The first line of input contains an integer T, denoting the number of test cases. The
first line of each test case is M and N, M is number of rows and N is number of
columns.
Output:
For each test case, print the number of paths.
Constraints:
1 ≤ T ≤ 30
1 ≤ M,N ≤ 10
Example:
Input
2
33
28
Output
6
8
CODE:
using namespace std;
int count(int i,int j,int n,int m)
if(i==n-1 || j==m-1)
return 1;
if(i>=n || j>=m)
return 0;
return (count(i+1,j,n,m) + count(i,j+1,n,m));
}
int main()
int t;
cin>>t;
while(t--)
int n,m;
cin>>n>>m;
cout<<count(0,0,n,m)<<endl;
return 0;
3. Combination Sum - Part 2
Given an array of integers A[] of size N and a sum B, find all unique combinations in
A where the sum is equal to B. Each number in A may only be used once in the
combination.
Note:
All numbers will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie,
a1 ≤ a2 ≤ … ≤ ak).
The combinations themselves must be sorted in ascending order.
Example 1:
Input:
N = 7
A = {9, 1, 2, 7, 6, 1, 5}
B = 8
Output: (1 1 6)(1 2 5)(1 7)(2 6)
Explaination: These are the only possible
combinations for getting sum 8.
Example 2:
Input:
N = 5
A = {8, 1, 8, 6, 8}
B = 12
Output: Empty
Explainatioin: We cannot obtain sum 12
from the given elements.
Your Task:
You don't need to read input r print anything. Your task is to complete the function
combinationSum() which takes the array A[], the length of the array N and the
sum B as input parameters and returns all the combinations, otherwise, if there is no
combination present it returns an empty list.
Expected Time Complexity: O(2N)
Expected Auxiliary Space: O(2N)
Constraints:
0 < N < 13
0 <= A[i] <= 9
0 < B <= 30
CODE:
// Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution{
public:
void combination(vector<int>& candidates, int target, vector<int> curr, vector<vector<int>>& result, int idx) {
if(target < 0)
return;
if(target == 0) {
result.push_back(curr);
return;
for(int i = idx; i<candidates.size(); i++) {
if(i > idx && candidates[i] == candidates[i-1])
continue; //ignore duplicate elements
curr.push_back(candidates[i]);
combination(candidates, target-candidates[i], curr, result, i+1);
curr.pop_back();
vector<vector<int>> combinationSum(vector<int> &candidates, int N, int B){
vector<vector<int>> result;
vector<int> curr;
sort(candidates.begin(), candidates.end()); //because we will ignore duplicate elements
combination(candidates, B, curr, result, 0);
return result;
};
// { Driver Code Starts.
int main()
int t;
cin>>t;
while(t--)
int N, x, B;
cin>>N;
vector<int> A;
for(int i = 0;i < N;i++)
{
cin>>x;
A.push_back(x);
cin>>B;
Solution ob;
vector<vector<int>> result;
result = ob.combinationSum(A, N, B);
if(result.size() == 0)
cout<<"Empty"<<endl;
else{
for(int i = 0;i < result.size(); i++){
cout<<"(";
for(int j = 0; j < result[i].size();j++){
cout<<result[i][j];
if(j < result[i].size() - 1)
cout<<" ";
cout<<")";
cout<<endl;
return 0;
}
4. Special Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: Prints 'A' on screen
Key 2: (Ctrl-A): Select screen
Key 3: (Ctrl-C): Copy selection to buffer
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been
printed.
Find maximum numbers of A's that can be produced by pressing keys on the special
keyboard N times.
Example 1:
Input: N = 3
Output: 3
Explaination: Press key 1 three times.
Example 2:
Input: N = 7
Output: 9
Explaination: The best key sequence is
key 1, key 1, key 1, key 2, key 3,
key4, key 4.
Your Task:
You do not need to read input or print anything. Your task is to complete the
function optimalKeys() which takes N as input parameter and returns the maximum
number of A's that can be on the screen after performing N operations.
Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(N)
Constraints:
1 < N < 75
CODE:
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution{
public:
unsigned long long int optimalKeys(int N){
if (N <= 6)
return N;
// An array to store result of subproblems
int screen[N];
int b; // To pick a breakpoint
// Initializing the optimal lengths array for uptil 6 input
// strokes.
int n;
for (n = 1; n <= 6; n++)
screen[n - 1] = n;
// Solve all subproblems in bottom manner
for (n = 7; n <= N; n++) {
// Initialize length of optimal string for n keystrokes
screen[n - 1] = 0;
// For any keystroke n, we need to loop from n-3 keystrokes
// back to 1 keystroke to find a breakpoint 'b' after which we
// will have ctrl-a, ctrl-c and then only ctrl-v all the way.
for (b = n - 3; b >= 1; b--) {
// if the breakpoint is at b'th keystroke then
// the optimal string would have length
// (n-b-1)*screen[b-1];
int curr = (n - b - 1) * screen[b - 1];
if (curr > screen[n - 1])
screen[n - 1] = curr;
}
return screen[N - 1];
};
// { Driver Code Starts.
int main(){
int t;
cin>>t;
while(t--){
int N;
cin>>N;
Solution ob;
cout<<ob.optimalKeys(N)<<"\n";
return 0;
5. Josephus problem
Given the total number of persons n and a number k which indicates that k-1 persons
are skipped and kth person is killed in circle in a fixed direction.​
The task is to choose the safe place in the circle so that when you perform these
operations starting from 1 place in the circle, you are the last one remaining
st
and survive.
Example 1:
Input:
n = 3 k = 2
Output: 3
Explanation: There are 3 persons so
skipping 1 person i.e 1st person 2nd
person will be killed. Thus the safe
position is 3.
Example 2:
Input:
n = 5 k = 3
Output: 4
Explanation: There are 5 persons so
skipping 2 person i.e 3rd person will
be killed. Thus the safe position is 4.
Your Task:
You don't need to read input or print anything. You are required to complete
the function josephus () that takes two parameters n and k and returns an integer
denoting safe position.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= k, n <= 20
CODE:
#include <bits/stdc++.h>
using namespace std;
int josephus(int n, int k);
int main() {
int t;
cin>>t;//testcases
while(t--)
int n,k;
cin>>n>>k;//taking input n and k
//calling josephus() function
cout<<josephus(n,k)<<endl;
return 0;
}// } Driver Code Ends
/*You are required to complete this method */
int josephus(int n, int k)
if(n==1)
return 1;
return ((josephus(n-1,k)+k-1)%n+1);
//Your code here
}
