|
Given an integer N, denoting the size of a circle where first N integers are placed in clockwise order such that j and (j+1) are adjacent, and 1 and N are also adjacent. Given an integer K (K < N), the task is to find if the last remaining value is odd or even when in each turn the Kth element from the start (i.e., 1) is removed and it is performed till only one element remains,
Examples:
Input: N = 5, K = 1
Output: Odd
Explanation: Here K = 1 it means first position element is removed from 5 integer circular array i.e. [ 1, 2, 3, 4, 5]→[2, 3, 4, 5] and repeat this step until only one integer remains i.e.[ 2, 3, 4, 5]→[ 3, 4, 5]→[ 4, 5]→[5]. Hence last integer is odd.
Input: N = 3, K = 3
Output: Even
Approach: The problem can be solved based on the following observation:
Observations:
- If K = 1: All numbers from 1 to N-1 are deleted and only N remains
- If K = 2: All numbers from 2 to N are deleted and only 1 remains.
- If K > 2: All numbers from K to N are deleted. Remaining numbers are from 1 to K-1. So in each turn when elements are deleted it follows pattern like 1, 3, 5, . . . because the size of the list decreases by 1 after each iteration and total numbers till the next odd number also decreases by 1. So all the odd elements get deleted first and then the even values. So the last remaining value is always an even number.
Follow the steps mentioned below to implement the observation:
- Check the value of K and N.
- Based on their values, decide which of the above cases is applicable.
- Return the parity of the element thus obtained.
Below is the implementation of the above approach:
C++
<?php
function parity($N, $K)
{
if (($K == 1 && ($N % 2 != 0)) || $K == 2)
return 1;
return 0;
}
$N = 5;
$K = 1;
if (parity($N, $K)!=0)
echo "Odd";
else
echo "Even";
?>
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
