Problem of the day
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.
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.
For each test case, print the integer present at position ‘K’.
Print the output of each test case in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= N <= 10^12
1 <= K <= N
Time Limit: 1 sec
2
7 4
5 3
7
5
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.
2
6 2
7 3
3
5
Try to think of the brute force approach to solve the problem.
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:
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).
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).
Interview problems
simplest way to solve this problem using cpp
#include <bits/stdc++.h>
int findInteger(int n, int k)
{
// Write your code here
vector<int>a1;//odd
vector<int>a2;//even
vector<int>a3;//ans
for(int i=1;i<=n;i++){
if(i%2==0){
a2.push_back(i);
}
else{
a1.push_back(i);
}
}
a1.insert(a1.end(),a2.begin(),a2.end());
return a1[k-1];
}
Interview problems
Python 100% passing
def findInteger(n, k):
mid = n // 2
# If n is odd then mid = mid + 1
if n % 2 != 0:
mid += 1
# If k <= mid then the answer is from the odd part which is in the first half
if k <= mid:
return 2 * k - 1 # for odd
# Else the answer is in the second half
else:
k -= mid
return 2 * k # for even
Interview problems
using python
def findInteger(n, k):
# Write your code here
o=[]
e=[]
for i in range(1,n+1):
if(i%2==0):
e.append(i)
else:
o.append(i)
l=o+e
count=0
for i in range(0,len(l)):
count=count+1
if(count==k):
return (l[i])
pass
Interview problems
Very Easy C++ Solution
#include <bits/stdc++.h>
int findInteger(int n, int k)
{
int mid=n/2;
//if n is odd then mid =mid+1
if(n%2!=0){
mid+=1;
}
//if k<=mid then the answer is from odd part which is in first half
if(k<=mid){
return 2*k-1; //for odd
}
//else the answer is in 2nd half
else{
k-=mid;
return 2*k; //for even
}
}
Interview problems
JAVA Optimal solution
int d=n/2;
//checking n is even or odd if odd increase d by 1
if(n%2==1)
d++;
if(k<=d)
return 2*(k-1)+1;
else
k-=d;
return 2*k;
Interview problems
Brute Force and Optimal Solution :
Brute Force Approach :
Time Complexity : O(N);
Space Complexity : O(N);
vector<int>ans ;
for(int i = 1 ; i <= n ; i++){
if(i % 2 != 0 && i != 0){
ans.push_back(i);
}
}
for(int i = 1 ; i <= n ; i++){
if(i % 2 == 0 && i != 0){
ans.push_back(i);
}
}
return ans[k - 1 ] ;
Optimal Approach :
Time Complexity : O(1);
Space Complexity : O(1);
Interview problems
EASY CPP
#include <bits/stdc++.h>
int findInteger(int n, int k)
{
int d=n/2;
if(n%2) d++;
if(k<=d) return 2*(k-1)+1;
else{
k-=d;
return 2*k;
}
}
Interview problems
Find Integer
#include <bits/stdc++.h>
int findInteger(int n, int k)
{
// Write your code here
int mid =(n+1)/2;
if(k<=mid){
return 2*k-1;
}
return 2*(k-mid);
}Interview problems
All the test cases are passed
import java.util.* ;
import java.io.*;
public class Solution {
public static int findInteger(int n, int k) {
// Write your code here
if (k <= (n + 1) / 2) {
// kth integer is an odd number
return 2 * k - 1;
} else {
// kth integer is an even number
return 2 * (k - (n + 1) / 2);
}
}
}
Interview problems
C++ Solution || All test Cases passed || Solution with comments
Time Complexity: O(1)
Space complexity: O(1)
#include <bits/stdc++.h>
using namespace std;
int findInteger(int n, int k)
{
// Write your code here
int mid = n / 2;
// If n is odd increase the middle point
if (n % 2 != 0)
{
mid += 1;
}
int result = 0;
// If k is less than middle point
if (k <= mid)
{
// Storing the (k - 1)th odd number
result = (k - 1)* 2 + 1;
}
else
{
// Store the offest from middle point in k
k -= mid;
// Storing the (k - 1)th even number
result = (k - 1)* 2 + 2;
}
return result;
}
All tags 
Sort by