Last Updated: 9 Dec, 2020

Find Integer

Easy

Asked in company

Solve now

Problem statement

You are given two integers, ‘N’ and ‘K’. Assume numbers from 1 to ‘N’ are arranged such that all odd numbers (in ascending order) are present first and then come to all even numbers (also in ascending order).

You need to find the integer at position ‘K’ (numbering of positions starts from 1).

For example:

You are given ‘N’ as 7 and ‘K’ as 4.  Numbers from 1 to 7 are arranged as [1, 3, 5, 7, 2, 4, 6], and the number at position 4 is 7. So, the answer is 7.

Input Format:

The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case consists of two space-separated integers, ‘N’ and ‘K’, representing the total number of integers and the position of the integer to find.

Output Format:

For each test case, print the integer present at position ‘K’.

Print the output of each test case in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^12
1 <= K <= N

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will maintain an array to store the numbers. We will insert all the odd numbers from 1 to N in ascending order and then insert all the remaining even numbers in ascending order from 1 to N in the array. To find the element at position K, return the number at position K - 1 in the array (because numbering positions are from 1).

Algorithm:

Create an array, newArray.
Iterate num from the numbers 1 to N. For each number num in the loop.
- If num is not divisible by 2, then insert num in newArray.
Iterate num from the numbers 1 to N again, for each number num in the loop
- If num is divisible by 2, then insert num in newArray.
At last, return the element at position K - 1, in newArray. So, we will return newArray[K - 1].

Solve now

02 Approach

In this approach, we know the position of the last odd number is at the middle of the array. We will check if K is more than N / 2, then we can find (K - N / 2) even number from 1. Otherwise, if K is less than half of N we can directly find Kth Odd number from 1.

To find any even number at the index position from 1 we can use the following formula:

2*index + 2

To find any odd number at the index position from 1 we can use the following formula:

2*index + 1

Algorithm:

Set mid as the quotient when N is divided by 2.
If N is divisible by 2, then increase mid by 1.
Check If K is greater than mid.
- Set result as (K - 1) * 2 + 1.
Otherwise, if K is less than or equal to mid.
- Set K equal to K minus mid.
- Set result as (K - 1) * 2 + 2.
Finally, return the variable result.

Solve now