Given an array of integers and a window size K, find the number of distinct elements in every window of size K of the given array.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains the N-size of the array and the K-size of the window. The second line contains N integers - elements of the array.Output FormatFor each test case, print the number of distinct elements in every window of size K, separated by a new line.Constraints30 points1 <= N <= 1001 <= K <= N70 points1 <= N <= 100001 <= K <= NGeneral Constraints1 <= T <= 1000-100 <= ar[i] <= 100ExampleInput35 3-2 -4 -2 4 -210 73 -4 -3 -4 -2 0 2 -2 6 017 13-5 -1 4 8 -5 -3 -4 7 4 -4 0 8 0 -2 3 2 5Output2 3 26 5 6 58 9 9 10 11
Question
Given an array of integers and a window size K, find the number of distinct elements in every window of size K of the given array.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines. The first line of each test case contains the N-size of the array and the K-size of the window. The second line contains N integers - elements of the array.Output FormatFor each test case, print the number of distinct elements in every window of size K, separated by a new line.Constraints30 points1 <= N <= 1001 <= K <= N70 points1 <= N <= 100001 <= K <= NGeneral Constraints1 <= T <= 1000-100 <= ar[i] <= 100ExampleInput35 3-2 -4 -2 4 -210 73 -4 -3 -4 -2 0 2 -2 6 017 13-5 -1 4 8 -5 -3 -4 7 4 -4 0 8 0 -2 3 2 5Output2 3 26 5 6 58 9 9 10 11
Solution
This problem can be solved using a sliding window approach and a hash map. Here are the steps:
- Initialize an empty hash map and a counter for distinct elements.
- Iterate over the first K elements of the array. For each element, if it's not in the hash map, increment the counter and add it to the hash map with a count of 1. If it's already in the hash map, just increment its count.
- Print the counter, which represents the number of distinct elements in the first window.
- For each remaining element in the array, do the following:
- Remove
Similar Questions
Given an array of unique integer elements, print all the subsets of the given array in lexicographical order.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array and the second line contains the elements of the array.Output FormatFor each test case, print the subsets of the given array in lexicographical order, separated by new line. Print an extra newline between output of different test cases.Constraints1 <= T <= 1001 <= N <= 100 <= A[i] <= 100ExampleInput335 15 3 257 96 43 15 8 23 Output3 3 5 3 5 15 3 15 5 5 15 15 57 57 96 96 3 3 8 3 8 15 3 8 15 23 3 8 23 3 15 3 15 23 3 23 8 8 15 8 15 23 8 23 15 15 23 23
Given an array of size 3X+1, where every element occurs three times, except one element, which occurs only once. Find the element that occurs only once.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array (of the form 3X + 1) and second line contains the elements of the array.Output FormatFor each test case, print the number which occurs only once, separated by new line.Constraints30 points1 <= T <= 1001 <= N <= 10370 points1 <= T <= 1001 <= N <= 106ExampleInput2105 7 8 7 7 9 5 9 5 9710 20 20 30 20 30 30Output810
how many windows would exist in an array with N elements and window size K a)N+K+1B)N-K-1C)N-K+1D)N+K-1
You are given an array of integers. For each element in the array, find the number of smaller elements on the right side and print the total count.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array. The second line contains the elements of the array.Output FormatFor each test case, print the sum of count of smaller elements on right side of each element in the array, separated by new line.Constraints30 points1 <= N <= 10370 points1 <= N <= 105General Constraints1 <= T <= 100-104 <= A[i] <= 104ExampleInput254 10 54 11 8615 35 25 10 15 12Output410ExplanationTest Case 1Smaller Elements on right side of 4 : 0Smaller Elements on right side of 10 : 1Smaller Elements on right side of 54 : 2Smaller Elements on right side of 11 : 1Smaller Elements on right side of 8 : 0Total Count = 0 + 1 + 2 + 1 + 0 = 4Test Case 2Smaller Elements on right side of 15 : 2Smaller Elements on right side of 35 : 4Smaller Elements on right side of 25 : 3Smaller Elements on right side of 10 : 0Smaller Elements on right side of 15 : 1Smaller Elements on right side of 12 : 0Total Count = 2 + 4 + 3 + 0 + 1 + 0 = 10
You are given an array of N elements. All elements of the array are in range 1 to N-2. All elements occur once except two numbers, which occur twice. Your task is to find the two repeating numbers.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array and second line contains the elements of the array.Output FormatPrint the 2 repeated numbers in sorted manner, for each test case, separated by new line.Constraints30 points1 <= T <= 1004 <= N <= 10370 points1 <= T <= 1004 <= N <= 106ExampleInput281 3 2 3 4 6 5 5101 5 2 8 1 4 7 4 3 6Output3 51 4
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.