sam
BAN USER- 1of 1 vote
AnswersGiven an array of N positive integers, N being even, and a number K, find out if it is possible
- sam in India
to form pairs of the numbers present in the array such that the sum of numbers in each pair is
divisible by K.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAlice and Bob are playing a game. The game is played as follows :
- sam in India
- There are N piles of coins on the table. Pile i has A[i] coins.
- In each turn, each player can pick up 1 or more coins from the leftmost non-empty pile.
- If a player picks up a coin from pile i , all coins from piles 0 to i-1 should have been taken.
- The person who picks up the last coin loses the game.
Alice and Bob play the game alternately. Alice plays first. Given the number of piles N and the
number of coins Ai in pile i, you have to determine which player will win the game, assuming
both play optimally.| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Brain Teasers
There is a simple logic to solve this, follow the below steps
1) Start with the first number and insert in array A
2) keep moving as long as it is in increasing order
3) The moment an item is skipped, store the first skipped index and move on by skipping any drops and inserting only increasing values to array A as step2 only
Now if there is an item skipped, start another iteration with that skipped index value saving it to array B and keep moving as long as it is in increasing order by dropping lower values and adding sequence values to Array B.
Return larger of Array A or B
The above solution wont work, as the intent is to find that .. all the elements in different pairs should be divisible by K. Example:
A = 1,2, 3, 6
K = 3,
=> (1,,2), (3,6)
=> 1+2 = 3%3 = 0
=> 3+ 6 = 9%3 = 0
Not just one pair, all the elements must be part of a pair.
Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}
This will print out the ranks.
Complexity O(n)
Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}
This will print out the ranks.
Complexity O(n)
Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}
This will print out the ranks.
Complexity O(n)
Input Array arr[6, 3, 9]
Find max element = 9
create another array tarr of size 9 all items initialized to -1;
Take rank counter int count = 0;
for(int i = 0; i < arr.Length; i++)
{
tarr[arr[i]] = count++;
}
for(int i = 0; i < tarr.length; i++)
{
if(tarr[i]!= -1)
{
print(tarr[i]);
}
}
This will print out the ranks.
Complexity O(n)
time Complexity = O(n), space complexity = O(n)
- sam May 10, 2013