Only One Operator (Posted on 2007-08-26)

	Submitted by Praneeth
Rating: 4.3333 (3 votes)
Solution:	(Hide)
1) XOR - bitwise logical operator and "Subtraction" 2) i) For XOR: a) n = 3 mod 4. b) This logic doesn't work only for n=2^k. ii) For Subtraction: a) n = 0 mod 4 or 3 mod 4. b) for all n. Explanation: 1)Write 1,2,..,7 in binary form. 001 010 011 100 101 110 111 There are exactly 4 1's at ith position, for every i. XOR of numbers from 1 to 7 is 0. We know x XOR x =0. Let f(n): XOR of 1st n natural numbers and missing number be x and chosen numbers be a1,a2,...and a6. f(7)=0 =>a1 XOR a2 XOR ....XOR a6 XOR x = 0. XOR x on both sides. x=a1 XOR a2 XOR a3 ... XOR a6. To find the missing number, XOR all the chosen numbers. 2) If you choose numbers from 1 to 4*k-1, there will be even number of 1's at ith position, for every i.It works for n=4*k-1 since f(4*k-1)=0. i) f(4*n)=f(4*n-1) XOR 4*n. f(4*n-1)=0 If no. of bits of 4*n is greater than 4*n-1, 4*n can't be expressed in terms of natural numbers from 1 to 4*n-1. ii) f(4*n+1)=f(4*n-1) XOR 4*n XOR 4*n+1. 4*n XOR 4*n+1 = 1. So, f(4*n+1)=f(4*n-1) XOR 1. The missing number can be found from the chosen numbers by XORing all the chosen numbers and again XORing the result with 1. f(4*n+2)=f(4*n-1) XOR (4*n) XOR 4*n+1 XOR 4*n+2. If the number to be expressed is 4*n+2, then Use f(4*n+2)=f(4*n-1) XOR 4*n XOR 3. else Use f(4*n+2)=f(4*n-1) XOR 1 XOR 4*n+2. and use same logic of XORing them before. from i) and ii) we can say that only for n=2^k (where k is a positive integer), this logic won't work.

	Subject	Author	Date
	Part 1 Solution	Brian Smith	2007-08-28 10:43:08
	No Subject	Praneeth	2007-08-27 02:49:06
	re(3): Part (1)	Praneeth	2007-08-27 02:31:58
	re(2): Part (1)	Penny	2007-08-27 02:27:40
	re: Part (1)	Praneeth	2007-08-27 02:03:12
	re: Part (1)	Penny	2007-08-26 21:16:56
	Part (1)	Penny	2007-08-26 17:15:41