UNIT-III
Rubric: 10m Code + 5m Viva +
5m Record
MEDIUM
15 Marks
Session: 59:59
Bubblewrap Sandbox Active
Problem Statement
Given a sorted array of N integers in non-decreasing order, count the total occurrences of a target integer K using an efficient O(log N) algorithm.
Print the total frequency of K in the array, or 0 if K is not present.
Input Format
Line 1 contains two integers N and K.
Line 2 contains N sorted space-separated integers.
Output Format
Print the total number of times K appears in the array.
Constraints
1 <= N <= 2 * 10^5
-10^9 <= A[i], K <= 10^9
Status
Lang
Score
Time
Submitted
No prior submissions for this problem.
Ready
Click Run Code to evaluate against sample test
cases, or Submit Solution for full evaluation.
No compiler or execution errors recorded.
#include <stdio.h>
int lower_bound(int arr[], int n, int k) {
int l = 0, r = n, ans = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] >= k) { ans = mid; r = mid; }
else { l = mid + 1; }
}
return ans;
}
int upper_bound(int arr[], int n, int k) {
int l = 0, r = n, ans = n;
while (l < r) {
int mid = l + (r - l) / 2;
if (arr[mid] > k) { ans = mid; r = mid; }
else { l = mid + 1; }
}
return ans;
}
int main() {
int n, k;
if (scanf("%d %d", &n, &k) != 2) return 0;
int arr[200005];
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
int low = lower_bound(arr, n, k);
int high = upper_bound(arr, n, k);
printf("%d\n", high - low);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
if (!(cin >> n >> k)) return 0;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
auto low = lower_bound(a.begin(), a.end(), k);
auto high = upper_bound(a.begin(), a.end(), k);
cout << (high - low) << endl;
return 0;
}
import java.util.Scanner;
import java.util.Arrays;
public class Main {
static int lower(int[] a, int k) {
int l = 0, r = a.length, ans = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] >= k) { ans = mid; r = mid; } else { l = mid + 1; }
}
return ans;
}
static int upper(int[] a, int k) {
int l = 0, r = a.length, ans = a.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (a[mid] > k) { ans = mid; r = mid; } else { l = mid + 1; }
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) return;
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
System.out.println(upper(a, k) - lower(a, k));
}
}
import sys
import bisect
def main():
lines = sys.stdin.read().split()
if not lines:
return
n = int(lines[0])
k = int(lines[1])
a = [int(x) for x in lines[2:n+2]]
low = bisect.bisect_left(a, k)
high = bisect.bisect_right(a, k)
print(high - low)
if __name__ == "__main__":
main()