Given an array of integers with size 2N+1 such that N elements appear twice in arbitrary positions and 1 element appears only once. Devise an algorithm to find the lonely element. Ex : {1 2 4 5 1 4 2} Answer : 5 courtesy: Syed Wali Hamza Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Think of some bit manipulation techniques. Hit again for solution. Solution: Note the properties of XOR : 1. A ^ A = 0 2. 0 ^ A = A 3. A ^ (B ^ C) = (A ^ B) ^ C Thus we just XOR all integers to finally get the lonely element since all others will be made 0 for repeating twice. Complexity: 1. Space: O(1) 2. Time: O(N) int lonely_element(int input[], int N){ int result=0, i=0; for(i=0; i<N; i++) result ^= input[i]; return result; }

Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted. For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false. courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: No hint this time. Hit again for solution. Solution: Simply find out the maximum and minimum in one pass and check if N == (max - min + 1) Complexity: 1. Space: O(1) 2. Time: O(N) int check_range(int input[], int N){ int max = input[0], min = input[0], i; for(i=1; i<N; i++){ if(input[i] < min) min=input[i]; if(input[i] > max) max=input[i]; } return (max - min + 1) == N; }

Given an array of size N which contains all the numbers from 1 to N-1. Find the number which is repeated in O(N) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to N-1 ? courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: No hint this time. Hit again for solution. Solution: For integers use sum to find the repeated number. For floating numbers, use Hash tables. Complexity: 1. Space: O(1) [O(K), K >> N for hash table] 2. Time: O(N) int repetition_int(int input[], int N){ int i=0, sum=0; for(i=0; i<N; i++) sum += input[i]; return sum - (N*(N-1)/2); } float repetition_float(float input[], int N){ int i; for(i=0; i<N; i++){ if(hash_table_exists(input[i])) return input[i]; hash_table_insert(input[i]); } return -1.0; }

You are walking down a path when you come to two doors. Opening one of the doors will lead you to a life of prosperity and happiness, while opening the other door will lead to a life of misery and sorrow. You don't know which door leads to which life. In front of the doors are two twin brothers who know which door leads where. One of the brothers always lies, and the other always tells the truth. You don't know which brother is the liar and which is the truth-teller. You are allowed to ask one single question to one of the brothers (not both) to figure out which door to open. What question should you ask? Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Doesn't the question name ring a bell itself. Hit again for solution. Solution: Ask "If I asked your brother what the good door is, what would he say ?". Both would point to wrong door.

You have two sand hourglasses, one that measures exactly 4 minutes and one that measures exactly 7 minutes. You need to measure out exactly 2 minutes. Using only these two hourglasses, how can you measure out exactly 2 minutes ? Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Just think what type of actions can be responsbile for such result? Hit again for solution. Solution: 7x - 4y = 2 we have a simple soultion, x=2 and y=3 We have 7*2 - 4*3 = 2 So we start both simultaneously. When 4 completes invert it, next invert 7 when done, next invert 4 when done again twice. Time remaining for 7 to finish is 2 minutes now.