Distinct Elements in WindowMax Score: 100Given 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 11ExplanationSelf Explanatory
Question
Distinct Elements in WindowMax Score: 100Given 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 11ExplanationSelf Explanatory
Solution
This problem is about finding the number of distinct elements in every window of size K in a given array. Here are the steps to solve this problem:
-
Initialize a variable to keep track of the distinct elements in the current window. This can be done using a set or a dictionary in most programming languages.
-
Iterate over the array from the 0th index to the Kth index and add each element to the set or dictionary. This will give you the number of distinct elements in the first window.
-
For each subsequent window, remove the first element of the previous window from the set or dictionary and add the next element from the array. This can be done in a loop that starts from K and ends at the length of the array.
-
After each iteration, print the size of the set or dictionary, which represents the number of distinct elements in the current window.
-
Repeat steps 3 and 4 until you have iterated over the entire array.
This algorithm has a time complexity of O(N), where N is the length of the array, because each element is visited once. The space complexity is O(K), where K is the size of the window, because at most K elements are stored in the set or dictionary at any time.
Similar Questions
iven an array of numbers and a window of size k. Print the maximum of numbers inside the window for each step as the window moves from the beginning of the array.Input FormatInput contains the array size, no of elements and the window sizeOutput FormatPrint the maximum of numbersConstraints1 <= size <= 1000 Sample Input 181 3 5 2 1 8 6 93
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
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 integers, find the largest number that can be constructed by concatenating all the elements 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 N - the size of the array and the second line contains N integers - the elements of the array.Output FormatFor each test case, print the largest number that can be constructed by concatenating all the elements of the given array, separated by a new line.Constraints1 <= T <= 10001 <= N <= 10000 <= ar[i] <= 1000ExampleInput3849 73 58 30 72 44 78 23469 9 57 60240 4Output78737258494430239696057440
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
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.