Count Distinct Elements in Every Window of Size K

By | | , ,
Leave a comment

Count Distinct Elements in Every Window of Size K.

Given an array of n integers and an integer k (k is always smaller or equal to n).  Return the count of distinct elements in all windows (or in all sub-arrays) of size k.

For example –

   Example 1:

  Input: {1, 5, 9, 3, 3, 7, 3},   k = 3

  Output: {3, 3, 2, 2, 2}

1st window {1, 5, 9}, Distinct elements are 3.

2nd window {5, 9, 3}, Distinct elements are 3.

3rd window {9, 3, 3}, Distinct elements are 2.

4th window {3, 3, 7}, Distinct elements are 2.

5th window {3, 7, 3}, Distinct elements are 2.

   Example 2:

  Input: {1, 4, 7, 7},   k = 2

  Output: {2, 2, 1}

1st window {1, 4}, Distinct elements are 2.

2nd window {4, 7}, Distinct elements are 2.

3rd window {7, 7}, Distinct elements are 1.

→

Find Square Root of an Integer

By | | , ,
Leave a comment

Find Square Root of an Integer. How to calculate square root in java without sqrt function.

Given an integer x (non-negative integer). Write a code to compute the square root of x.

If x is not a perfect square in that case return floor of square root of x (floor(sqrt(x))).

NOTE: Do not use the sqrt function from the standard library.

For example –

Example 1:

           Input: 4

Output: 2

Example 2:

          Input: 11

          Output: 3

The square root of 11 is 3.316624 but we have returned the integer part only after truncating the decimal digits.

floor(3.316624) is 3

Example 3:

         Input: 17

         Output: 4

The square root of 17 is 4.12310. Floor(4.12310) is 4.

→