Counting Rock Samples | TCS Codevita 2020
John is a geologist, and he needs to count rock samples in order to send it to a chemical laboratory. He has a problem. The laboratory only accepts rock samples by a range of sizes in ppm (parts per million). John needs your help. Your task is to develop a program to get the number of rocks in each range accepted by the laboratory.
Problem Statement: Given an array samples[] denoting sizes of rock samples and a 2D array ranges[], the task is to count the rock samples that are in the range ranges[i][0] to ranges[i][1], for every possible 1 <= i <= N.
Examples:
Input: samples[] = {345, 604, 321, 433, 704, 470, 808, 718, 517, 811}, ranges[] = {{300, 380}, {400, 700}}
Output: 2 4
Explanation:
Range [300, 380]: Samples {345, 321} lie in the range. Therefore, the count is 2.
Range [400, 700]: Samples {433, 604, 517, 470} lie in the range. Therefore, the count is 4.Input: samples[] = {400, 567, 890, 765, 987}, ranges[] = {{300, 380}, {800, 1000}
Output: 0 2
Approach: The idea is to iterate samples[] for every ranges[i] and count the number of samples that lie in the specified ranges. Follow the steps below to solve the problem:
- Traverse the array ranges[].
- For each row ranges[i], traverse the array samples[] and count the number of rock samples lying in the range [ranges[i][0], ranges[i][1]].
Below is the implementation of the above approach:
C++
// C++ program of the // above approach #include<bits/stdc++.h> using namespace std; void findRockSample(vector<vector< int >>ranges, int n, int r, vector< int >arr) { vector< int >a; // Iterate over the ranges for ( int i = 0; i < r; i++) { int c = 0; int l = ranges[i][0]; int h = ranges[i][1]; for ( int j = 0; j < arr.size(); j++) { if (l <= arr[j] && arr[j] <= h) c += 1; } a.push_back(c); } for ( auto i:a) cout << i << " " ; } // Driver Code int main() { int n = 5; int r = 2; vector< int >arr = { 400, 567, 890, 765, 987 }; vector<vector< int >>ranges = { { 300, 380 }, { 800, 1000 } }; // Function call findRockSample(ranges, n, r, arr); } // This code is contributed by Stream_Cipher |
Java
// Java program of the // above approach import java.util.*; import java.io.*; class GFG{ // Function to find the rock // samples in the ranges static ArrayList<Integer>findRockSample( int ranges[][], int n, int r, int arr[]) { ArrayList<Integer> a = new ArrayList<>(); // Iterate over the ranges for ( int i = 0 ; i < r; i++) { int c = 0 ; int l = ranges[i][ 0 ]; int h = ranges[i][ 1 ]; for ( int j = 0 ; j < arr.length; j++) { if (l <= arr[j] && arr[j] <= h) c += 1 ; } a.add(c); } return a; } // Driver Code public static void main(String args[]) { int n = 5 ; int r = 2 ; int arr[] = { 400 , 567 , 890 , 765 , 987 }; int ranges[][] = { { 300 , 380 }, { 800 , 1000 } }; ArrayList<Integer> answer = new ArrayList<>(); // Function call answer = findRockSample(ranges, n, r, arr); for ( int i = 0 ; i < answer.size(); i++) System.out.print(answer.get(i) + " " ); System.out.println(); } } // This code is contributed by bikram2001jha |
Python3
# Python3 program of the # above approach # Function to find the rock # samples in the ranges def findRockSample(ranges, n, r, arr): a = [] # Iterate over the ranges for i in range (r): c = 0 l, h = ranges[i][ 0 ], ranges[i][ 1 ] for val in arr: if l < = val < = h: c + = 1 a.append(c) return a # Driver Code if __name__ = = "__main__" : n = 5 r = 2 arr = [ 400 , 567 , 890 , 765 , 987 ] ranges = [[ 300 , 380 ], [ 800 , 1000 ]] # Function Call print ( * findRockSample(ranges, n, r, arr)) |
C#
// C# program of the // above approach using System.Collections.Generic; using System; class GFG{ // Function to find the rock // samples in the ranges static void findRockSample( int [,]ranges, int n, int r, int [] arr) { List< int > a = new List< int >(); // Iterate over the ranges for ( int i = 0; i < r; i++) { int c = 0; int l = ranges[i, 0]; int h = ranges[i, 1]; for ( int j = 0; j < arr.Length; j++) { if (l <= arr[j] && arr[j] <= h) c += 1; } a.Add(c); } foreach ( var i in a) { Console.Write(i + " " ); } } // Driver Code public static void Main() { int n = 5; int r = 2; int []arr = { 400, 567, 890, 765, 987 }; int [,]ranges = { { 300, 380 }, { 800, 1000 } }; // Function call findRockSample(ranges, n, r, arr); } } // This code is contributed by Stream_Cipher |
Javascript
<script> // Javascript program of the above approach // Function to find the rock // samples in the ranges function findRockSample(ranges, n, r, arr) { let a = []; // Iterate over the ranges for (let i = 0; i < r; i++) { let c = 0; let l = ranges[i][0]; let h = ranges[i][1]; for (let j = 0; j < arr.length; j++) { if (l <= arr[j] && arr[j] <= h) c += 1; } a.push(c); } for (let i = 0; i < a.length; i++) { document.write(a[i] + " " ); } } let n = 5; let r = 2; let arr = [ 400, 567, 890, 765, 987 ]; let ranges = [ [ 300, 380 ], [ 800, 1000 ] ]; // Function call findRockSample(ranges, n, r, arr); </script> |
0 2
Time Complexity: O(N2)
Auxiliary Space: O(1)