bool setisfy(vector<vector<int>> &mat, int i, int j, int num) {
for(int x= 0; x<9; x++) {
if(mat[i][x] == num || mat[x][j] == num)
return false;
}
int str = i-i%3, stc = j-j%3;
for(int a=0; a<3; a++){
for(int b=0;b<3; b++) {
if(mat[str+a][stc+b] == num)
return false;
}
}
return true;
}
bool solve(vector<vector<int>> &mat) {
for(int i=0; i<9; i++) {
for(int j=0; j<9; j++) {
if(mat[i][j] == 0) {
for(int num = 1; num<=9; num++) {
if(setisfy(mat, i, j, num)) {
mat[i][j] = num;
if(solve(mat)) return true;
mat[i][j] = 0;
}
}
return false;
}
}
}
return true;
}
// Function to find a solved Sudoku.
void solveSudoku(vector<vector<int>> &mat) {
// code here
solve(mat);
}Month: January 2025
GFG PTOD | 30 Jan | N-Queen Problem | Hard | Backtracking
void solve(int colm, int n, vector<bool> &col, vector<bool> &ldiag, vector<bool> &rdiag, vector<vector<int>> &ans, vector<int> &res) {
for(int i=0; i<n; i++) {
if(colm == n) {
ans.push_back(res);
return;
}
if(!col[i] && !ldiag[colm-i + n-1] && !rdiag[i+colm]) {
res.push_back(i+1);
col[i] = true;
ldiag[colm-i+n-1] = true;
rdiag[i+colm] = true;
solve(colm+1, n, col, ldiag, rdiag, ans, res);
res.pop_back();
col[i] = false;
ldiag[colm-i+n-1] = false;
rdiag[i+colm] = false;
}
}
}
vector<vector<int>> nQueen(int n) {
// code here
vector<bool>col(n, false);
vector<bool>ldiag(2*n-1, false);
vector<bool>rdiag(2*n-1, false);
vector<vector<int>> ans;
vector<int> res;
solve(0, n, col, ldiag, rdiag, ans, res);
return ans;
}GFG PTOD | 29 Jan | Implement Pow
double power(double b, int e) {
// code here
int n = abs(e);
double res = 1.0;
while(n>0) {
if(n%2 == 0) {
b *=b;
n=n/2;
} else {
res *= b;
n--;
}
}
if(e<0) res = double(1.0)/res;
return res;
}GFG PTOD | 28 Jan | Permutations of a String
void helper(int i, int n, string &s, unordered_set<string> &st, string &cur) {
if(cur.size() == n) {
st.insert(cur);
return;
}
for(int j=i; j<n; j++) {
swap(s[i], s[j]);
cur.push_back(s[i]);
helper(i+1, n, s, st, cur);
cur.pop_back();
swap(s[i], s[j]);
}
}
vector<string> findPermutation(string &s) {
// Code here there
unordered_set<string> st;
string cur;
helper(0, s.size(), s, st, cur);
vector<string> res(st.begin(), st.end());
return res;
}GFG PTOD | 26 Jan | Remove loop in Linked List
void removeLoop(Node* head) {
// code here
Node* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
// check if fast and slow pointer at head node
if(fast == slow) {
while(fast->next != slow)
fast = fast->next;
}
else {
while(slow->next !=fast->next) {
slow = slow->next;
fast = fast->next;
}
}
fast->next = NULL;
}
}
}GFG PTOD | 25 Jan | Find the first node of loop in linked list
Node* findFirstNode(Node* head) {
// your code here
Node* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
while(slow!=fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}GFG PTOD | 24 Jan | Detect Loop in linked list
// Function to check if the linked list has a loop.
bool detectLoop(Node* head) {
// your code here
Node *slow=head, *fast=head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) return true;
}
return false;
}GFG PTOD | 23 Jan | Clone List with Next and Random
Node *cloneLinkedList(Node *head) {
// Write your code here
if(head == NULL) return head;
Node *cur = head;
// Step 1: create new node and make a link from first to create map
while(cur) {
Node *newNode = new Node(cur->data);
newNode->next = cur->next;
cur->next = newNode;
cur = newNode->next;
}
// Step 2: Assign random pointer to head2
cur = head;
Node *head2 = cur->next;
while(cur!=NULL) {
if(cur->random == NULL) cur->next->random = NULL;
else cur->next->random = cur->random->next;
cur = cur->next->next;
}
//Step 3: Make proper link of head and head2 and return head2
cur=head;
while(cur) {
Node *tmp = cur->next;
cur->next = tmp->next;
if(tmp->next) tmp->next = tmp->next->next;
cur=cur->next;
}
return head2;
}GFG PTOD | 25 Jan | Find the first node of loop in linked list
Node* findFirstNode(Node* head) {
// your code here
Node* slow = head, *fast = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if(slow == fast) {
slow = head;
while(slow!=fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}GFG PTOD | 22 Jan 2025 | Add Number Linked Lists
class Solution {
public:
Node* reverseList(struct Node* head) {
struct Node* cur = head, *prev = NULL, *next = NULL;
while(cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
Node* removeZero(struct Node* head) {
while(head != NULL && head->data == 0)
head = head->next;
return head;
}
Node* addTwoLists(Node* num1, Node* num2) {
// code here
num1 = removeZero(num1);
num2 = removeZero(num2);
num1 = reverseList(num1);
num2 = reverseList(num2);
Node *ret = NULL, *cur=NULL;
int carry = 0;
while(num1 || num2 || carry != 0) {
int sum = carry;
if(num1) {
sum += num1->data;
num1 = num1->next;
}
if(num2) {
sum += num2->data;
num2 = num2->next;
}
carry = sum/10;
Node *tmp = new Node(sum % 10);
if(ret == NULL) {
ret = tmp;
cur = tmp;
} else {
cur->next = tmp;
cur = cur->next;
}
}
return reverseList(ret);
}
};