Choose filters to find knowledge

Python Program To Find Minimum number of items to be delivered

def getMin(N, A, k): for i in range(1, max(A)+1): tours = 0 for j in range(0, len(A)): if(A[j]% i == 0): tours += A[j]/i else: tours += A[j]//i + 1 if(tours <= k): return i return "Not Possible" N = 10 A = [1, 34,76,23,2,6,90,30,45,65] k = 50 print(getMin(N, A, k))

Find the winner in nim-game

Let’s start the solution step by step. We have total of three option for the XOR of array and this game. XOR of array is already 0: In this case Alice will unable to make a move and hence Alice is winner. XOR of array is not zero: Now, in this case we have two options, either size of array will be odd or even. CASE A: If the array size is odd then for sure Bob will win the game. CASE B: If the array size is even then Alice will win the game. Above conclusion can be proved with the help of mathematical induction. Let A[] = {1} i.e. size of array is odd and XOR of array is non-zero: In this case Alice can select element 1 and then A[] will become empty and hence XOR of array can be considered as zero. Resulting Bob as winner. Let size of array is even and XOR of array is non-zero. Now we can prove that Alice can always find an element to remove such that XOR of remaining elements of array will be non-zero. To prove this lets start from the contradiction i.e. suppose whatever element you should choose XOR of remaining array must be zero. So, let A1 Xor A2 Xor … An = X and n is even. As per our contradiction hypothesis, Ai Xor X = 0 for 1<= i <= n. Calculate XOR of all X Xor Ai (i.e. n equations), After taking XOR of all n equations we have X Xor X…Xor X (n-times) = 0 as N is even. Now, also we have A1 Xor A2 Xor.. An = 0 but we know A1 Xor A2…Xor = X. This means we have at least one element in even-size array such that after its removal XOR of remaining elements in non-zero. Let size of array is even and XOR of array is non-zero. Alice can not remove an element Ai such that xor of remaining number is zero, because that will make Bob win. Now, take the other case when the xor of remaining N?1 number is non-zero. As we know that N?1 is even and from the induction hypothesis, we can say that the position after the current move will be a winning position for Bob. Hence, it is a losing position for Alice.

Activity Selection Problem

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used for optimization problems. An optimization problem can be solved using Greedy if the problem has the following property: At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem. If a Greedy Algorithm can solve a problem, then it generally becomes the best method to solve that problem as the Greedy algorithms are in general more efficient than other techniques like Dynamic Programming. But Greedy algorithms cannot always be applied. For example, Fractional Knapsack problem (See this) can be solved using Greedy, but 0-1 Knapsack cannot be solved using Greedy. Following are some standard algorithms that are Greedy algorithms. 1) Kruskal’s Minimum Spanning Tree (MST): In Kruskal’s algorithm, we create a MST by picking edges one by one. The Greedy Choice is to pick the smallest weight edge that doesn’t cause a cycle in the MST constructed so far. 2) Prim’s Minimum Spanning Tree: In Prim’s algorithm also, we create a MST by picking edges one by one. We maintain two sets: a set of the vertices already included in MST and the set of the vertices not yet included. The Greedy Choice is to pick the smallest weight edge that connects the two sets. 3) Dijkstra’s Shortest Path: The Dijkstra’s algorithm is very similar to Prim’s algorithm. The shortest path tree is built up, edge by edge. We maintain two sets: a set of the vertices already included in the tree and the set of the vertices not yet included. The Greedy Choice is to pick the edge that connects the two sets and is on the smallest weight path from source to the set that contains not yet included vertices. 4) Huffman Coding: Huffman Coding is a loss-less compression technique. It assigns variable-length bit codes to different characters. The Greedy Choice is to assign least bit length code to the most frequent character. The greedy algorithms are sometimes also used to get an approximation for Hard optimization problems. For example, Traveling Salesman Problem is a NP-Hard problem. A Greedy choice for this problem is to pick the nearest unvisited city from the current city at every step. This solutions don’t always produce the best optimal solution but can be used to get an approximately optimal solution.

Check if an array is Wave Array

#include <iostream> using namespace std; bool isWaveArray(int arr[], int n) { bool result = true; if (arr[1] > arr[0] && arr[1] > arr[2]) { for (int i = 1; i < n - 1; i += 2) { if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) { result = true; } else { result = false; break; } } if (result == true && n % 2 == 0) { if (arr[n - 1] <= arr[n - 2]) { result = false; } } } else if (arr[1] < arr[0] && arr[1] < arr[2]) { for (int i = 1; i < n - 1; i += 2) { if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) { result = true; } else { result = false; break; } } if (result == true && n % 2 == 0) { if (arr[n - 1] >= arr[n - 2]) { result = false; } } } return result; } int main() { int arr[] = { 1, 3, 2, 4 }; int n = sizeof(arr) / sizeof(int); if (isWaveArray(arr, n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0; }

Variation in Nim Game

Nim is a famous game in which two players take turns removing items from distinct piles. During each turn, a player must remove one or more items from a single, non-empty pile. The winner of the game is whichever player removes the last item from the last non-empty pile. Now, For each non-empty pile, either player can remove zero items from that pile and have it count as their move; however, this move can only be performed once per pile by either player. Given the number of items in each pile, determine who will win the game; Player 1 or player 2. If player 1 starts the game and both plays optimally. Approach: Grundy number for each pile is calculated based on the number of stones.To compensate the zero move we will have to modify grundy values we used in standard nim game. If pile size is odd; grundy number is size+1 and if pile size is even; grundy number is size-1. We XOR all the grundy number values to check if final Grundy number(G) of game is non zero or not to decide who is winner of game. Explanation: Grundy number of a state is the smallest positive integer that cannot be reached in one valid move. So, we need to calculate mex value for each n, bottom up wise so that we can induce the grundy number for each n. where n is the pile size and valid move is the move that will lead the current player to winning state. Winning state: A tuple of values from where the current player will win the game no matter what opponent does. (If G!=0) Losing state: A tuple of values from where the current player will loose the game no matter what opponent does. (If G=0)

Number of solutions of n = x + n ⊕ x

#include <bits/stdc++.h> using namespace std; int numberOfSolutions(int n) { int c = 0; for (int x = 0; x <= n; ++x) if (n == x + n ^ x) ++c; return c; } int main() { int n = 3; cout << numberOfSolutions(n); return 0; }