CODEWITHSUNDEEP
c++algorithm
Frosty
Frosty

Reputation: 500

Select m friends among n colleagues with given constraints.(Coding ques)

Jack has n colleagues and m friends in his office. Jack brought one gift for each of his m friends. After knowing that, all of his n colleagues demanded gifts from him. But Jack wanted to give gifts only to his friends. So, he told them to stand in a circle around him, where the 1st colleague stands next to the nth one. Then Jack will follow a strategy to distribute the gifts. He will start by giving gift to some person b, and will continue to give gift to every sth person. After someone receives gift, he does not leave the circle. Jack noticed the positions of his friends, and now he wants to choose b and s in such a way that, only and all of his friends get those gifts.

Input Format: The first line of input contains 2 space separated integers, n and m, number of Jack’s colleagues and number of Jack’s friends. The next line contains m space separated integers, the positions of Jack’s friends.

Output Format: Output suitable b and s to execute Jack’s plan. If no suitable answer exists, output “impossible” ( without the quotes ). If there are multiple solutions, print any of them. Constraints:

1<=n<=10^9
1<=m<=10^6

m<=n

positions of Jack’s friends will be given in increasing order. Sample Input

5 3
3 4 5

Sample Output

3 1

Upvotes: 2

Views: 131

Answers (2)

hk6279
hk6279

Reputation: 1879

Perform front jumping and backward jumping may be a solution. If there is less than or equal to two friends, the result is true. If there is more than two friends, apply following solution.

1. Pick the first person and create front jumping gap list.

For example, n=19, friends = 1 2 3 11 12 13. The front jumping gap list is [1,2,10,11,12]

2. Start at the person we choose ,for each gap in the gap list

A) Create an jumping index that hold the states of friends in list if the jumping has cover it.

B) Start front gap jumping. Jumping value = Current position + gap. If jumping value > n, jumping value = jumping value - n. Repeat jumping until the jumping index cover all friend or the jumping position is not for a friend.

For example, we pick person 1 and gap 1. Obviously, person 1 is covered. Mark jumping index of person 1 to covered. then jump to person 2 (1+1). Spot this friend position exist. Mark jumping index of person 2 to covered.

C) If Some of the friend is not covered by 2(B), then perform backward jump from the person we choose with the gap we choose. Jumping value = Current position - gap. If jumping value < 1 (starting point), jumping value = jumping value + n. Repeat backward jumping until the jumping index cover all friend or the jumping position is not for a friend.

For example, with person 1 and gap 1. We try to look for person 0 (1-1). 0 is less than 1, so do adjustment with 0+19 = 19. Person 19 do not exist and we end here for this gap.

D) Check if this gap cover all friends. If true, find the person b by jumping backward, return the person as b and gap as s.If not, check next gap and perform 2(B) and 2(C).

3. Start at the person we choose, perform backward jumping

Similarly, we are doing the whole process like step 1 and 2, but instead of moving forward, we move backward.

  • First, create a backward jumping list by n + friend position at the person we choose - friend position in the list.

For example, n=19, friends = 1 2 3 11 12 13. The backward jumping gap list is [7,8,9,17,18]

  • Then perform backward jump. Unlike front jumping, we do backward jumping first. That mean perform 2(A) ->2(C) -> 2(B) -> 2(D) on all gap of backward jump.

    4. No solution

    If both step 2 and 3 can not cover all friends, there is no solution at all.

Solution analysis

First of all, b in [1,n] and s in ([1,n-1] and [-(n-1),-1]). s can be positive moving

Assume there is a solution, then there exist person b, then person b+s, person b+2s, ... person b+(m-1)s.

Picking any friend from the list has three possibility:

  • Person at head of the list (person b)
  • Person at middle of the list (person b+rs where r in [1,m-2])
  • Person at end of the list (person b+(m-1)s)

If chosen person is person at head of the list, it can be solved by one of the 2(A)/(3) process.

If chosen person is person at middle of the list, it can be solved by one of the 2(A)+2(B) process.

If chosen person is person at end of the list, it can be solved by one of the (3) process.

If not handle by above, that mean no solution.

Upvotes: 1

Ali Akber
Ali Akber

Reputation: 3800

You can calculate all the differences between adjacent friends.
Complexity : O(m)

Then observe the calculated value :

  1. if all the differences are same then you can start from the first friend.
  2. if only one difference mismatches then you can start from mismatched position.

Example:

1 5 13 17
diff - 4(1st-2nd) 8(2nd-3rd) 4(3rd-4th) 4(4th-1st)

one mismatch in the 2nd difference. And you know 2nd difference is the distance between 2nd and 3rd friend. So you can start from the 3rd friend

  1. otherwise it's not possible

Upvotes: 2

Related Questions