#include <stdio.h>

	#define SIZE 20

	/////////////////////////////////////////////////////////////////////////////
	/*
		FOUNDATION EXAM QUESTION (Question 1):

		A company is looking to hire an employee based on answers to a questionnaire.
		The questionnaire has 20 yes/no questions (labeled from question 0 to question
		19) and an applicant’s set of responses is stored as a single integer such
		that the ith bit is set to 1 if the response to question i is yes, and it’s
		set to 0 if the response to question i is no. For example, if an applicant
		answered yes to questions 0, 2, 3, 5, 8, and 10 and no to the other 14
		questions, her responses would be stored as the single integer 1325, since
		00000000010100101101 = 1325. For all questions, the company prefers yes
		answers to no answers. However, since it’s unlikely that a candidate will
		answer yes to all of the questions, they have developed a modified scoring
		system for each candidate. The company has ranked each of the 20 questions in
		order of preference from most important to least important. This ranking is an
		array, preferences, that stores a permutation of the integers from 0 to 19,
		inclusive. For example, if preferences[0] = 8, preferences[1] = 10 and
		preferences[2] = 1, then the company cares most about the answer to question
		8, second most about the answer to question 10 and third most about the answer
		to question 1. A candidate's score is simply the maximum number of the most
		important questions they answered yes without a single no. For example, the
		sample candidate described above would have a score of 2, because she said yes
		to questions 8 and 10, but no to question 1, which was third on the preference
		list. Any candidate who said no to question 8 would be assigned a score of 0.
		Complete the function below so it returns the score of the applicant whose
		answers are stored in the formal parameter applicant. The formal parameter
		preferences is an array of size 20 which stores the order of importance of the
		questions as previously described. (Note: You must use bitwise operators to
		earn full credit for this question. Assume SIZE has been defined as 20.)
	*/

	int score(int preferences[], int applicant) {
		int i = 0;
		// Loops through the indexes of preferences starting at 0
		for (i = 0; i < SIZE; i++) {

			// 1 << preferences[i] will shift 1 left by preferences[i], which represents
			// the current question being checked. Use the bitwise & operator with
			// applicant to determine whether the applicant answered "yes" to that
			// question. If the result is greater than 0, the applicant answered yes and
			// we continue to the next most important question. If the result is 0, the
			// applicant answered no, so we stop and return how many important questions
			// were answered yes in a row.

			if (((1 << preferences[i]) & applicant) == 0)
				break;
		}
		return i;
	}

	///////////////////////////////////////////////////////////////////////////////////
	/*
		FOUNDATION EXAM QUESTION (Question 2):

		Imagine a dating website that asks each user 20 yes/no questions and stores
	their answers in a single integer in between 0 and 2^(20) -1, with the answer to
	the kth question stored in bit 2^(k-1) , with the bit 0 representing the answer
	no and the bit 1 representing the answer yes for the corresponding question. (So
	for example, if one person’s answers to questions 1, 3 and 4 were yes and the
	rest of the answers were no, the integer 1101 = 13 would be used to represent
	her 20 answers to the questions.) Consider the problem of finding the “best
	match” for a client out of a list of prospective matches. We consider a match A
	for the client to be better than match B if she shares more answers on
	corresponding questions with A than B. Write a function that takes in an integer
	representing the client’s answers, an array of integers storing the answers of
	potential matches, and the length of that array, which returns the index into
	the array storing the best match for that client. If there are multiple best
	matches, you may return the index associated with any of them. A function has
	been given that you may call in your code, if you find it useful.
	*/

	int count(int mask);
	int bestMatch(int client, int *matches, int length) {
		int bestIndex = 0;
		int bestCount = -1;
		for (int i = 0; i < length; i++) {
			int numMatches = 20 - count(client ^ matches[i]);
			if (numMatches > bestCount) {
				bestCount = numMatches;
				bestIndex = i;
			}
		}
		return bestIndex;
	}

	int count(int mask) {
		int res = 0, i;
		for (i = 0; i < 32; i++)
			if ((mask & (1 << i)) != 0)
				res++;
		return res;
	}

	///////////////////////////////////////////////////////////////////////////////////
	/*
		FOUNDATION EXAM QUESTION (Question 3):

	There are a total of 25 cards, numbered 0 through 24. We can represent a set of
	cards with a single integer by setting the i th bit to 1 if the set contains
	card i, and setting the bit to 0 otherwise. For example, the set of cards {2, 6,
	7} would be stored as the integer 196, since 196 = 2^7 + 2^6 + 2^2 . Two sets of
	cards are disjoint, if and only if no card appears in both sets. Complete the
	function below so that it returns 1 if the sets of cards represented by the
	integers set1 and set2 are disjoint, and returns 0 if they are not disjoint.
	(For example, disjoint(196, 49) should return 1 because 49 = 2^5 + 2^4 + 2^0 , and
	there is no common value in the two sets {2, 6, 7} and {0, 4, 5}. On the other
	hand, disjoint(196, 30) should return 0 because 30 = 2^4 + 2^3 + 2^2 + 2^1 , so that
	card number 2 is included in both sets 196 and set 30.)
	// Pre-condition: set1 and set2 are bitmasks in between 0 and
	// (1<<25)-1.
	// Post-condition: Returns 1 if the two bitmasks are disjoint,
	// meaning that the sets they represent don't have
	// any items in common, and returns 0 otherwise, if
	// the two represented sets do have common items.
	*/

	int disjoint(int set1, int set2) { return ((set1 & set2) == 0); }

	////////////////////////////////////////////////////////////////////////////////////

	/*
		FOUNDATION EXAM QUESTION (Question 3):

	Imagine the task of painting a picket fence with 20 pickets. Let each picket be
	numbered from 0 to 19, from left to right and initially each is painted white. A
	pattern is 5 pickets long and can be placed with the pattern's left end aligned
	with any picket in between number 0 and number 15, inclusive. (If you line the
	pattern up with any of the pickets 16 through 19, the right end of the pattern
	goes past the right end of the fence and this isn't allowed.) Below is a picture
	of an example pattern, with the 3 of the 5 possible pickets painted:

	If this pattern was lined up with picket number 4, then pickets 4, 5 and 7 would
	get painted. Think of the process as a placing a stamp on a portion of the whole
	fence. We can represent this pattern with the integer 11 (2^0 + 2^1 + 2^3
	), the integer where bits 0, 1 and 3 are set to 1. The bit positions represent,
	relative to the left end of the pattern, which positions have paint on them.
	One way to paint a fence with a pattern is to line up the pattern with a few
	different picket numbers and apply the pattern. For example, if we lined up this
	pattern with the pickets at positions 1 and 4, then the pickets that would be
	painted would be at positions 1, 2, 4, 5 and 7. (Notice that painting an
	individual picket more than once leaves it still painted.) Complete the function
	below so that it takes in an integer, pattern, in between 0 and 31, inclusive,
	representing the pattern, an integer array, paintLoc, which stores the locations
	to line up the pattern with for painting, and paintLen, representing the length
	of the array paintLoc and returns a single integer storing the state of the
	painted fence (for each picket number, k, that is painted, bit k in the returned
	integer should be set to 1). Each of the values in paintLoc will be distinct
	integers in between 0 and 15, inclusive.
	*/

	// This problem is difficult to understand at first, so here is a breakdown
	// of what each variable represents:
	//
	// pattern: an integer representing a 5-bit mask. Each bit represents whether
	// a picket relative to the left edge of the pattern is painted (1) or not (0).
	//
	// paintLoc[]: an array of integers indicating where the left edge of the
	// pattern should be placed on the fence. For each value paintLoc[i], the
	// pattern is shifted left by paintLoc[i] to line it up with the correct
	// pickets.
	//
	// paintLen: the number of locations stored in the paintLoc array.
	//
	// Example:
	// Suppose pattern = 00101 (binary) and paintLoc[] = {2, 6}.
	// Start with fence = 00000000000000000000.
	//
	// First iteration (paintLoc[0] = 2):
	// pattern << 2  = 00000000000000010100
	// fence | value = 00000000000000010100
	//
	// Second iteration (paintLoc[1] = 6):
	// pattern << 6  = 00000000000001010000
	// fence | value = 00000000000001110100
	//
	// The final returned integer has bits 3, 5, 7, and 9 set to 1,
	// meaning those pickets are painted.

	int paintFence(int pattern, int paintLoc[], int paintLen) {
		int fence = 0;
		for (int i = 0; i < paintLen; i++) {
			fence = fence | (pattern << paintLoc[i]);
		}
		return fence;
	}

	////////////////////////////////////////////////////////////////////////////////////

	/*
		FOUNDATION EXAM QUESTION (Question 4):

	In the game of NIM, there are several piles with stones and two players
	alternate taking 1 or more stones from a single pile, until there are no more
	stones left. The person who takes the last stone wins. It turns out that if it's
	someone's turn, if they play optimally, they can win as long as the bitwise XOR
	of all of the number of stones in each pile is not equal to 0. Write a function
	that takes in an array of values representing the number of stones in the piles
	of NIM and the length of that array, and returns 1, if the current player can
	win, and 0 otherwise, assuming both players play optimally.
	*/

	int canWinNIM(int piles[], int numPiles) {
		int total = 0;
		for (int i = 0; i < numPiles; i++) {
			total = total ^ piles[i];
		}
		return (total != 0);
	}

	////////////////////////////////////////////////////////////////////////////////////

	/*
		FOUNDATION EXAM QUESTION (Question 5):

	Two useful utility functions when dealing with integers in their binary
	representation are (a) int lowestOneBit(int n) - returns the value of the lowest
	bit set to 1 in the binary representation of n. (eg. lowestOneBit(12)returns 4,
	lowestOneBit(80)returns 16.) (b) int highestOneBit(int n) - returns the value of
	the highest bit set to 1 in the binary representation of n. (eg.
	highestOneBit(12)returns 8, highestOneBit(80)returns 64.) Note: You may assume
	that the input is less than 109 . The largest positive bit value in an integer
	is equal to 230 > 109
	.
	The pre-condition for the first function is that n must be a positive integer.
	The pre-condition for the second function is that n must be a positive integer
	less than 109 . Write both of these functions in the space below. To earn full
	credit, you must use bitwise operators when appropriate. (Namely, there are ways
	to solve this question without using bitwise operators, but these solutions will
	NOT receive full credit.)
	*/

	// Keep shifting 1 left until the first bit that is 1 is found
	int lowestOneBit(int n) {
		int rtn = 1;
		while ((n & rtn) == 0) {
			rtn = rtn << 1;
		}
		return rtn;
	}

	// Highest set bit is the greatest power of 2 less than or equal to the integer
	int highestOneBit(int n) {
		int rtn = 1;
		while ((rtn << 1) <= n) {
			rtn = rtn << 1;
		}
		return rtn;
	}

	////////////////////////////////////////////////////////////////////////////////////

	/*
		FOUNDATION EXAM QUESTION (Question 6):

	In this problem we will consider buying a collection of 20 figurines, labeled 0
	through 19, inclusive. The figurines come in packages. Each package has some
	non-empty subset of figurines. We can represent the contents of a single package
	using an integer in between 1 and (2^20) – 1, inclusive, where the bits that are
	on represent which figurines are in the package. For example, the integer 22 =
	2^4 + 2^2 + 2^1 , would represent a package with figurines 1, 2 and 4. Each
	month, one package comes out. You greedily buy every package until you have all
	20 figurines. Write a function that takes in an array of integers, packages, and
	its length, n, where packages[i] stores an integer representing the contents of
	the package on sale during month i, and returns the number of months you will
	have to buy packages to complete the set. It is guaranteed that each figurine
	belongs to at least one of the packages and that each value in the array
	packages is in between 1 and (2^20) -1, inclusive. For full credit, you must use
	bitwise operators.
	*/

	int monthsTillComplete(int packages[], int n) {
		// It has said that the value of each package is between 1 and (2^20) -1
		// where (2^20) -1 represents the value of bitmask with all 20 bits set
		// This value can be written as (1<<20)-1 [1 shifted 20 bits left - 1]
		int numAllCollected = (1 << 20) - 1;

		// Now we can have some tracker to determine if all bits have been set to 1
		// and continue updating every month
		int tracker = 0;
		int month = 0;
		while (tracker != numAllCollected && month < n) {
			tracker |= packages[month];
			month++;
		}
		return month;
	}

	////////////////////////////////////////////////////////////////////////////////////

	// Additional example question: Write a function that takes in an integer and prints the
	// binary version of that integer from left to right as it would be read

	// Takes in a decimal integer greater than 0 and prints each bit
	void printEachBit(int num) {
		if (num == 0)
			return;

		// shifts bits right one removing rightmost bit (Ex. 1101 becomes 110)
		int newNum = num >> 1;

		// Recursive call which shifts
		printEachBit(newNum);

		// This will return 1 if the rightmost bit is one, otherwise returns 0
		int lastBit = num & 1;

		// Prints on backtrack in order to print left to right
		printf("%d", lastBit);
	}