Find Integer

Easy
0/40
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in company
HCL Technologies

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
7 4
5 3
Sample Output 1:
7
5
Explanation:
For the first test case, the numbers from 1 to 7 are arranged as [1, 3, 5, 7, 2, 4, 6], and the number at position 4 is 7. Hence the answer is 7.

For the second test case, the numbers from 1 to 5 are arranged as [1, 3, 5, 2, 4], and the number at position 3 is 5. Hence the answer is 5.
Sample Input 2:
2
6 2
7 3
Sample Output 2:
3
5
Hint

Try to think of the brute force approach to solve the problem.

Approaches (2)
Brute Force

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].
Time Complexity

O(N), Where N is the given integer.

 

We are traversing from 1 to N once, which takes O(N) time complexity. In total, we are traversing from 1 to N twice, so the overall time complexity becomes O(N + N) = O(N).

Space Complexity

O(N), Where N is the given integer.

 

We are maintaining an array of 1 to N integers that will take O(N) space. So the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Find Integer
Full screen
Console