This is like first pass of Quick sort.
make a[k-1] pivot and at the end of first pass you will have the a[k-1]'s position.
(k-1 cause 1-indexing)
Can someone tell where is the error?
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main60 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-->0) {
int n = Integer.parseInt(br.readLine());
String s[] = br.readLine().trim().split(" ");
int k = Integer.parseInt(br.readLine());
k = Integer.parseInt(s[k-1]);
Arrays.sort(s);
for(int i =0; i<n; i++) {
if(s[i].equals(String.valueOf(k))) {
System.out.println(i+1);
break;
}
}
}
}
}I have used a binary search approach which does not work, I mean it gives me a time limit exceeded error but, a linear search works just fine, what is the problem, can anybody please shed some light on this? As far as I am able to understand, consider the example input
1
5
1 2 3 9 4
1
In this case on doing binary search on the sorted array, my algorithm for binary search will do 3 iterations, whereas linear search will do it in constant time since it’s the first element of the array. Maybe the testcases have such edges in them. If there is something else please let me know. I am also providing my source that has both the solutions in it.
// Gotta figure out why this shit wouldn't run with binary search
#include <iostream>
#include <algorithm>
using namespace std;
int binary_search(int start_index, int end_index, int query, int *arr){
int mid = (start_index + end_index) / 2;
if(arr[mid] == query) return mid;
if(arr[mid] > query) return binary_search(start_index, mid, query, arr);
if(arr[mid] < query) return binary_search(mid, end_index, query, arr);
}
int main(){
int t, N, prev_index, search;
cin >> t;
for(int i = 0; i < t; i++){
cin >> N;
int playlist[N];
for(int j = 0; j < N; j++){
cin >> playlist[j];
}
cin >> prev_index;
int search = playlist[prev_index - 1];
sort(playlist, playlist+N);
for(int k = 0; k < N; k++){
if(playlist[k] == search) printf("%d\n", k+1);
}
// int curr_index = binary_search(0, N - 1, search, playlist);
// printf("%d\n", curr_index+1);
}
}
Thanks.
t = int(input())
while t > 0:
n = int(input())
myinupt = input()
arr = [int(num) for num in myinupt.split()]
k = int(input())
val = arr[k-1]
arr.sort()
for index, aval in enumerate(arr):
if aval == val:
print(index+1)
t = t - 1mid = mid + (low+high)/2;
It should work now I guess.
mid = mid + (start_index + end_index) / 2;
I guess it should work now.
Consider the test input:
1
3
3 20 100
1
1 Like
Bro it would be way better if u learn using STL in your codes…
for _ in range(int(input())):
tot_songs=int(input())
lens_songs = [int(item) for item in input().split()]
act_pos = int(input())
act_item = lens_songs[act_pos-1]
for i in range(tot_songs):
for j in range(tot_songs-i-1):
if lens_songs[j]>lens_songs[j+1]:
lens_songs[j] = lens_songs[j]*lens_songs[j+1]
lens_songs[j+1] = lens_songs[j]/lens_songs[j+1]
lens_songs[j] = lens_songs[j]/lens_songs[j+1]
for item in range(len(lens_songs)):
if lens_songs[item]==act_item:
print(item+1)
break
Can someone help me figure out what is wrong with this? This outputs the right results on my local but codechef won’t accept it as the answer
why isnt this working can anyone tell me
#include
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T;
cin>>T;
for(int i=0;i<T;i++)
{
int N,K;
int arr[N];
cin>>N;
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
cin>>K;
int song=arr[K];
sort(arr,arr+N);
int alpha=0;
for(alpha;alpha<N;alpha++)
{
if(arr[alpha]==song)
{
break;
}
}
cout<<alpha<<endl;
}
return 0;
}
import java.util.*;
class cf
{
static int calculate(long[] arr, int k)
{
long num = arr[k-1];
Arrays.sort(arr);
for(int i=0;i<arr.length;i++)
{
if(arr[i]==num)
return i+1;
}
return 0;
}
static Scanner input = new Scanner(System.in);
public static void main(String[] args) {
try
{
int t = input.nextInt();
int[] answers = new int[t];
for(int i=0;i<t;i++)
{
int n = input.nextInt();
long[] nums = new long[n];
for (int j=0;j<n;j++ )
{
nums[j] = input.nextInt();
}
int k = input.nextInt();
answers[i] = calculate(nums,k);
}
for(int an : answers)
System.out.println(an);
}
catch(Exception e)
{
return;
}
}
}
Why is this not working?
#include<bits/stdc++.h>
using namespace std;
int main() {
int t,n,k,c;
cin>>t;
while(t--){
cin>>n;
int ar[n];
for(int i=0;i<n;i++){
cin>>ar[i];
}
cin>>k;
c=ar[k-1];
sort(ar,ar+n);
for(int j=0;j<n;j++){
if(ar[j]==c)
cout<<j+1;
}
}
}It fails on the sample testcase (it outputs 341).
while(low<=high) // base looping condition in ur case it is wrong
Blockquote
#include<bits/stdc++.h>
using namespace std;
int binary_search(int a[],int n, int x){
int start = 0;
int end = n-1;
while(start < end){
int mid = (start) + (end-start)/2;
if(a[mid] == x)
return mid+1;
else if(a[mid] < x){
start = mid + 1;
}else{
end = mid - 1;
}
}
return -1;
}
int main(){
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int k;
cin >> k;
int song = a[k-1];
sort(a, a+n);
// for (int i = 0; i < n; i++)
// {
// cout << a[i];
// }
cout << binary_search(a, n, song) << endl;
}
return 0;
}
why is this code not working?
Consider the test input:
1
1
1
1
even if i add a condition at the start in the binary search
if(start == end)
{
cout<< 1;
}
Will it work?
Why don’t you try it and see? 
Right now i went with a different approach… to find the song in the sorted array
1 Like