Notes

Print all strings of n-bits

void generateAllStrings(int n, int i, vector<int> &currStr, vector<string> &strs) {
// Write your code here
int new_str= 1<<n;
for(int p=0;i<new_str;i++){
string str="";
for(int j=n-1;j>=0;j--){
str+=((i>>j)&1 ? "1":"0");
}
strs.push_back(str);
}
}

Print all string of n-bits with condition

void generateAllStrings(int n, int i, int k, vector<int> &currStr, vector<string> &strs)
{
int new_str= 1<<n;
for(int p=0;i<new_str;i++){
string str="";
for(int j=n-1;j>=0;j--){
str+=((i>>j)&1 ? "1":"0");
}
if(str[k]=='1'){
strs.push_back(str);
}
}
}

Pair with the given sum


bool pairSum(int *arr, int n, int k) {

int i=0;
int j=n-1;
for(i;i<j;){
if(arr[i]+arr[j]==k){
return 1;
}
else if((arr[i]+arr[j])<k){
i++;
}
else if((arr[i]+arr[j])>k){
j--;
}
}
return 0;
}

Tribal Tradition

int followsTradition(string motherName, string childName) {
// Write your code here
string ans=motherName+motherName;
for(int i=0;i<motherName.length();i++){
if(ans.substr(i,motherName.length())==childName){
return 1;
}
}
return 0;
}


Find all pairs with K difference


#include <set>
int getPairsCount(int arr[], int n, int k) {
// Write your code here
int count=0;
set<int> s;
for(int i=0;i<n;i++){
s.insert(arr[i]);
}
for(int i=0;i<n;i++){
if(s.count(arr[i]-k)){
count++;
}
}
return count;
}

Count number of ways to cover a distance

int totalWaysToDistance(int d, int k){
// Write your code here
//int* p=new int[d+1];
int* dp=new int [d+1];
dp[0]=1;
for(int i=1;i<=d;i++){
for(int j=1;j<=k && j<=i;j++){
dp[i]+=dp[i-j];
}
}
return dp[d];
}

Rat in a Maze Problem

#include <vector>
bool isValid(int row, int col, int size, int maze[][50], vector<vector<bool>>& visited) {
return (row >= 0 && row < size && col >= 0 && col < size && maze[row][col] == 0 && !visited[row][col]);
}
void findPaths(int row, int col, int size, int maze[][50], vector<vector<bool>>& visited, int& numPaths) {
if (row == size - 1 && col == size - 1) {
numPaths++;
return;
}
int dr[] = {0, 1};
int dc[] = {1, 0};
for (int i = 0; i < 2; i++) {
int newRow = row + dr[i];
int newCol = col + dc[i];
if (isValid(newRow, newCol, size, maze, visited)) {
visited[newRow][newCol] = true;
findPaths(newRow, newCol, size, maze, visited, numPaths);
visited[newRow][newCol] = false;
}
}
}
int solveMaze(int maze[][50], int size) {
vector<vector<bool>> visited(size, vector<bool>(size, false));
int numPaths = 0;
findPaths(0, 0, size, maze, visited, numPaths);
return numPaths;
}