question.txt

(Asked by Amazon) TC O(N)
Q1. A professor went to a party. Being an erudite person, he classified the party into two categories. He proposed that if all the persons in the party are wearing different colored robes, then that is a girl’s only party. If we even get one duplicate color, it must be a boy’s party. The colors of the robes are represented by positive integers.
Input
The first line of each test case contains an integer T, denoting the no of test cases. Then T test cases follow. The first line of each test case contains an integer N denoting the number of people in the party. In the next line are N space separated values of Ai denoting the color of the robes.
Output
For each test case, print “BOYS” without quotes if it’s a boy’s party, else print “GIRLS”


i/p: 1 2 3 4 7
o/p: girls

i/p: 1 3 2 4 5 1
o/p: boys


Example
Input
2
5
1 2 3 4 7
6
1 3 2 4 5 1
Output
GIRLS
BOYS
Explanation:
In the first testcase, all the colors are unique so it's a GIRLS party.
In the second testcase, there are two colors 1. So it's a BOYS party.


(Asked By Samsung) TC O(N)
Q2. Shaggy has a frog Akki. Akki is very hungry and Shaggy decides to feed it by playing a little game. Akki is a special frog which can jump as far as it wants but has a special pattern: He starts at the point 0.
In his first turn, he can make a jump of 1 unit. Now for all consequent turns, if the frog is currently at a distance x (from the start), his jump will take him x units forward. Given a leaf at a distance N , you have to find if the frog can reach that leaf or not.
Input
	•	The first line contains number of test cases 'T' followed by 'T' non-negative integer 'x' denoting the distance.
Output:
	•	Output contains T line containing,for each test cases True if the frog Akki can reach that pillar and print False otherwise.


Example:
Input:
3
1
7
64
Output:
True
False
True



TC O(N)
Q3. Given an integer array A that contains only integers 0 and 1. Write a function to sort this array. Find a solution which scans the array only once. Don't use extra array.
You need to change in the given array itself. So no need to return or print anything.
Input format :
Sample Input :
7
0 1 1 0 1 0 1
Sample Output :
0 0 0 1 1 1 1



Q4. Anagram String e.g listen and silent. O(N)

Q5. Find the Missing Number O(N)
N Natural Number
6,1,2,4,5,7,9,8. 
Missing Number is 3