Skip to main content

Count distinct elements in every window of given size

Here given code implementation process.

/*
    Java Program
    Count distinct elements in every window of given size
*/
import java.util.HashMap;
public class DistinctCount
{
	// Function which is display array elements
	public void display(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print("  " + arr[i]);
		}
		System.out.print("\n");
	}
	// Count distinct elements in given window size
	public void countDistinctWindow(int[] arr, int n, int size)
	{
		// Display given array
      	System.out.print(" Array :");
		display(arr, n);
		if (n < size || size < 1)
		{
			System.out.print("\n Invalid window size : " + size + "\n");
			return;
		}
		// Use to collect frequency of array elements
		HashMap < Integer, Integer > store = new HashMap < Integer, Integer > ();
		// Define counter variable
		int result = 0;
		// Loop controlling variable
		int i = 0;
		// iterate the loop through by window size
		// Get first window
		for (i = 0; i < size; ++i)
		{
			if (store.containsKey(arr[i]))
			{
				store.put(arr[i], store.get(arr[i]) + 1);
			}
			else
			{
				store.put(arr[i], 1);
			}
		}
		System.out.print(" Result : ");
		System.out.print(" " + (store.size()));
		// Count distinct elements in another window
		for (i = size; i < n; ++i)
		{
			if (store.get(arr[i - size]) == 1)
			{
				// Need to remove element 
				// When it occurs only once
				store.remove(arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store.put(arr[i - size], store.get(arr[i - size]) - 1);
			}
			if (store.containsKey(arr[i]))
			{
				// Increase element frequency
				store.put(arr[i], store.get(arr[i]) + 1);
			}
			else
			{
				// Add new element
				store.put(arr[i], 1);
			}
			System.out.print("  " + (store.size()));
		}
	}
	public static void main(String[] arg)
	{
		DistinctCount task = new DistinctCount();
		// Define array of integer elements
		int[] arr = {
			7 , 2 , 7 , 2 , 1 , 4 , 5 , 1 , 6 , 4 , 3 , 3 , 5 , 5 , 5
		};
		// Get number of element
		int n = arr.length;
		int size = 5;
		task.countDistinctWindow(arr, n, size);
	}
}

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
// Include header file
#include <iostream>
#include <unordered_map>

using namespace std;
/*
    C++ Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	public:
		// Function which is display array elements
		void display(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << "  " << arr[i];
			}
			cout << "\n";
		}
	// Count distinct elements in given window size
	void countDistinctWindow(int arr[], int n, int size)
	{
		// Display given array
		cout << " Array :";
		this->display(arr, n);
		if (n < size || size < 1)
		{
			cout << "\n Invalid window size : " << size << "\n";
			return;
		}
		// Use to collect frequency of array elements
		unordered_map < int, int > store ;
		// Loop controlling variable
		int i = 0;
		// iterate the loop through by window size
		// Get first window
		for (i = 0; i < size; ++i)
		{
			if (store.find(arr[i]) != store.end())
			{
				store[arr[i]] = store[arr[i]] + 1;
			}
			else
			{
				store[arr[i]] = 1;
			}
		}
		cout << " Result : ";
		cout << " " << (store.size());
		// Count distinct elements in another window
		for (i = size; i < n; ++i)
		{
			if (store[arr[i - size]] == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.erase(arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store[arr[i - size]] = store[arr[i - size]] - 1;
			}
			if (store.find(arr[i]) != store.end())
			{
				// Increase element frequency
				store[arr[i]] = store[arr[i]] + 1;
			}
			else
			{
				// Add new element
				store[arr[i]] = 1;
			}
			cout << "  " << (store.size());
		}
	}
};
int main()
{
	DistinctCount task = DistinctCount();
	// Define array of integer elements
	int arr[] = {
		7 , 2 , 7 , 2 , 1 , 4 , 5 , 1 , 6 , 4 , 3 , 3 , 5 , 5 , 5
	};
	// Get number of element
	int n = sizeof(arr) / sizeof(arr[0]);
	int size = 5;
	task.countDistinctWindow(arr, n, size);
	return 0;
}

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
// Include namespace system
using System;
using System.Collections.Generic;
/*
    C# Program
    Count distinct elements in every window of given size
*/
public class DistinctCount
{
	// Function which is display array elements
	public void display(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write("  " + arr[i]);
		}
		Console.Write("\n");
	}
	// Count distinct elements in given window size
	public void countDistinctWindow(int[] arr, int n, int size)
	{
		// Display given array
		Console.Write(" Array :");
		display(arr, n);
		if (n < size || size < 1)
		{
			Console.Write("\n Invalid window size : " + size + "\n");
			return;
		}
		// Use to collect frequency of array elements
		Dictionary < int, int > store = new Dictionary < int, int > ();
		// Loop controlling variable
		int i = 0;
		// iterate the loop through by window size
		// Get first window
		for (i = 0; i < size; ++i)
		{
			if (store.ContainsKey(arr[i]))
			{
				store[arr[i]] = store[arr[i]] + 1;
			}
			else
			{
				store.Add(arr[i], 1);
			}
		}
		Console.Write(" Result : ");
		Console.Write(" " + (store.Count));
		// Count distinct elements in another window
		for (i = size; i < n; ++i)
		{
			if (store[arr[i - size]] == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.Remove(arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store[arr[i - size]] = store[arr[i - size]] - 1;
			}
			if (store.ContainsKey(arr[i]))
			{
				// Increase element frequency
				store[arr[i]] = store[arr[i]] + 1;
			}
			else
			{
				// Add new element
				store.Add(arr[i], 1);
			}
			Console.Write("  " + (store.Count));
		}
	}
	public static void Main(String[] arg)
	{
		DistinctCount task = new DistinctCount();
		// Define array of integer elements
		int[] arr = {
			7 , 2 , 7 , 2 , 1 , 4 , 5 , 1 , 6 , 4 , 3 , 3 , 5 , 5 , 5
		};
		// Get number of element
		int n = arr.Length;
		int size = 5;
		task.countDistinctWindow(arr, n, size);
	}
}

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
<?php
/*
    Php Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	// Function which is display array elements
	public	function display( & $arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo "  ". $arr[$i];
		}
		echo "\n";
	}
	// Count distinct elements in given window size
	public	function countDistinctWindow( & $arr, $n, $size)
	{
		// Display given array
		echo " Array :";
		$this->display($arr, $n);
		if ($n < $size || $size < 1)
		{
			echo "\n Invalid window size : ". $size ."\n";
			return;
		}
		// Use to collect frequency of array elements
		$store = array();
		// Loop controlling variable
		$i = 0;
		// iterate the loop through by window size
		// Get first window
		for ($i = 0; $i < $size; ++$i)
		{
			if (array_key_exists($arr[$i], $store))
			{
				$store[$arr[$i]] = $store[$arr[$i]] + 1;
			}
			else
			{
				$store[$arr[$i]] = 1;
			}
		}
		echo " Result : ";
		echo " ". (count($store));
		// Count distinct elements in another window
		for ($i = $size; $i < $n; ++$i)
		{
			if ($store[$arr[$i - $size]] == 1)
			{
				unset($store[$arr[$i - $size]]);
			}
			else
			{
				$store[$arr[$i - $size]] = $store[$arr[$i - $size]] - 1;
			}
			if (array_key_exists($arr[$i], $store))
			{
				$store[$arr[$i]] = $store[$arr[$i]] + 1;
			}
			else
			{
				$store[$arr[$i]] = 1;
			}
			echo "  ". (count($store));
		}
	}
}

function main()
{
	$task = new DistinctCount();
	// Define array of integer elements
	$arr = array(7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5);
	// Get number of element
	$n = count($arr);
	$size = 5;
	$task->countDistinctWindow($arr, $n, $size);
}
main();

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
/*
    Node Js Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	// Function which is display array elements
	display(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write("  " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Count distinct elements in given window size
	countDistinctWindow(arr, n, size)
	{
		// Display given array
		process.stdout.write(" Array :");
		this.display(arr, n);
		if (n < size || size < 1)
		{
			process.stdout.write("\n Invalid window size : " + size + "\n");
			return;
		}
		// Use to collect frequency of array elements

		var store = new Map();
		// Loop controlling variable
		var i = 0;
		// iterate the loop through by window size
		// Get first window
		for (i = 0; i < size; ++i)
		{
			if (store.has(arr[i]))
			{
				store.set(arr[i], store.get(arr[i]) + 1);
			}
			else
			{
				store.set(arr[i], 1);
			}
		}
		process.stdout.write(" Result : ");
		process.stdout.write(" " + (store.size));
		// Count distinct elements in another window
		for (i = size; i < n; ++i)
		{
			if (store.get(arr[i - size]) == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.delete(arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store.set(arr[i - size], store.get(arr[i - size]) - 1);
			}
			if (store.has(arr[i]))
			{
				// Increase element frequency
				store.set(arr[i], store.get(arr[i]) + 1);
			}
			else
			{
				// Add new element
				store.set(arr[i], 1);
			}
			process.stdout.write("  " + (store.size));
		}
	}
}

function main()
{
	var task = new DistinctCount();
	// Define array of integer elements
	var arr = [7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5];
	// Get number of element
	var n = arr.length;
	var size = 5;
	task.countDistinctWindow(arr, n, size);
}
main();

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
# 
#     Python 3 Program
#     Count distinct elements in every window of given size

class DistinctCount :
	#  Function which is display list elements
	def display(self, arr, n) :
		i = 0
		while (i < n) :
			print("  ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Count distinct elements in given window size
	def countDistinctWindow(self, arr, n, size) :
		#  Display given list
		print(" Array :", end = "")
		self.display(arr, n)
		if (n < size or size < 1) :
			print("\n Invalid window size : ", size )
			return
		
		#  Use to collect frequency of list elements
		store = dict()
		#  Loop controlling variable
		i = 0
		#  iterate the loop through by window size
		#  Get first window
		while (i < size) :
			if (arr[i] in store.keys()) :
				store[arr[i]] = store.get(arr[i]) + 1
			else :
				store[arr[i]] = 1
			
			i += 1
		
		print(" Result : ", end = "")
		print(" ", (len(store)), end = "")
		#  Count distinct elements in another window
		i = size
		while (i < n) :
			if (store.get(arr[i - size]) == 1) :
				#  Need to remove element
				#  When it occurs only once
				del store[arr[i - size]]
			else :
				#  Reduce element frequency
				store[arr[i - size]] = store.get(arr[i - size]) - 1
			
			if (arr[i] in store.keys()) :
				#  Increase element frequency
				store[arr[i]] = store.get(arr[i]) + 1
			else :
				#  Add new element
				store[arr[i]] = 1
			
			print("  ", (len(store)), end = "")
			i += 1
		
	

def main() :
	task = DistinctCount()
	#  Define list of integer elements
	arr = [7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5]
	#  Get number of element
	n = len(arr)
	size = 5
	task.countDistinctWindow(arr, n, size)

if __name__ == "__main__": main()

Output

 Array :   7   2   7   2   1   4   5   1   6   4   3   3   5   5   5
 Result :   3   4   5   4   4   4   5   4   4   3   2
#  Ruby Program
#  Count distinct elements in every window of given size

class DistinctCount 
	#  Function which is display array elements
	def display(arr, n) 
		i = 0
		while (i < n) 
			print("  ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  Count distinct elements in given window size
	def countDistinctWindow(arr, n, size) 
		#  Display given array
		print(" Array :")
		self.display(arr, n)
		if (n < size || size < 1) 
			print("\n Invalid window size : ", size ,"\n")
			return
		end

		#  Use to collect frequency of array elements
		store = Hash.new
		#  Loop controlling variable
		i = 0
		#  iterate the loop through by window size
		#  Get first window
		while (i < size) 
			if (store.key?(arr[i])) 
				store[arr[i]] = store[arr[i]] + 1
			else 
				store[arr[i]] = 1
			end

			i += 1
		end

		print(" Result : ")
		print(" ", (store.size()))
		#  Count distinct elements in another window
		i = size
		while (i < n) 
			if (store[arr[i - size]] == 1) 
				store.delete(arr[i - size])
			else 
				store[arr[i - size]] = store[arr[i - size]] - 1
			end

			if (store.key?(arr[i])) 
				store[arr[i]] = store[arr[i]] + 1
			else 
				store[arr[i]] = 1
			end

			print("  ", (store.size()))
			i += 1
		end

	end

end

def main() 
	task = DistinctCount.new()
	#  Define array of integer elements
	arr = [7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5]
	#  Get number of element
	n = arr.length
	size = 5
	task.countDistinctWindow(arr, n, size)
end

main()

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
import scala.collection.mutable._;
/*
    Scala Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	// Function which is display array elements
	def display(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Count distinct elements in given window size
	def countDistinctWindow(arr: Array[Int], n: Int, size: Int): Unit = {
		// Display given array
		print(" Array :");
		this.display(arr, n);
		if (n < size || size < 1)
		{
			print("\n Invalid window size : " + size + "\n");
			return;
		}
		// Use to collect frequency of array elements
		var store: Map[Int, Int] = Map();
		// Loop controlling variable
		var i: Int = 0;
		// iterate the loop through by window size
		// Get first window
		while (i < size)
		{
			if (store.contains(arr(i)))
			{
				store.addOne(arr(i), store.get(arr(i)).get + 1);
			}
			else
			{
				store.addOne(arr(i), 1);
			}
			i += 1;
		}
		print(" Result : ");
		print(" " + (store.size));
		// Count distinct elements in another window
		i = size;
		while (i < n)
		{
			if (store.get(arr(i - size)).get == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.remove(arr(i - size));
			}
			else
			{
				// Reduce element frequency
				store.addOne(arr(i - size), store.get(arr(i - size)).get - 1);
			}
			if (store.contains(arr(i)))
			{
				// Increase element frequency
				store.addOne(arr(i), store.get(arr(i)).get + 1);
			}
			else
			{
				// Add new element
				store.addOne(arr(i), 1);
			}
			print("  " + (store.size));
			i += 1;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: DistinctCount = new DistinctCount();
		// Define array of integer elements
		var arr: Array[Int] = Array(7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5);
		// Get number of element
		var n: Int = arr.length;
		var size: Int = 5;
		task.countDistinctWindow(arr, n, size);
	}
}

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
import Foundation
/*
    Swift 4 Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	// Function which is display array elements
	func display(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Count distinct elements in given window size
	func countDistinctWindow(_ arr: [Int], _ n: Int, _ size: Int)
	{
		// Display given array
		print(" Array :", terminator: "");
		self.display(arr, n);
		if (n < size || size < 1)
		{
			print("\n Invalid window size : ", size );
			return;
		}
		// Use to collect frequency of array elements
		var store = [Int: Int]();
		// Loop controlling variable
		var i: Int = 0;
		// iterate the loop through by window size
		// Get first window
		while (i < size)
		{
			if (store.keys.contains(arr[i]))
			{
				store[arr[i]] = store[arr[i]]! + 1;
			}
			else
			{
				store[arr[i]] = 1;
			}
			i += 1;
		}
		print(" Result : ", terminator: "");
		print(" ", (store.count), terminator: "");
		// Count distinct elements in another window
		i = size;
		while (i < n)
		{
			if (store[arr[i - size]] == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.removeValue(forKey: arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store[arr[i - size]] = store[arr[i - size]]! - 1;
			}
			if (store.keys.contains(arr[i]))
			{
				// Increase element frequency
				store[arr[i]] = store[arr[i]]! + 1;
			}
			else
			{
				// Add new element
				store[arr[i]] = 1;
			}
			print("  ", (store.count), terminator: "");
			i += 1;
		}
	}
}
func main()
{
	let task: DistinctCount = DistinctCount();
	// Define array of integer elements
	let arr: [Int] = [7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5];
	// Get number of element
	let n: Int = arr.count;
	let size: Int = 5;
	task.countDistinctWindow(arr, n, size);
}
main();

Output

 Array :   7   2   7   2   1   4   5   1   6   4   3   3   5   5   5
 Result :   3   4   5   4   4   4   5   4   4   3   2
/*
    Kotlin Program
    Count distinct elements in every window of given size
*/
class DistinctCount
{
	// Function which is display array elements
	fun display(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print("  " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	// Count distinct elements in given window size
	fun countDistinctWindow(arr: Array < Int > , n: Int, size: Int): Unit
	{
		// Display given array
		print(" Array :");
		this.display(arr, n);
		if (n < size || size < 1)
		{
			print("\n Invalid window size : " + size + "\n");
			return;
		}
		// Use to collect frequency of array elements
		var store = mutableMapOf<Int, Int>();
		// Loop controlling variable
		var i: Int = 0;
		// iterate the loop through by window size
		// Get first window
		while (i < size)
		{
			if (store.containsKey(arr[i]))
			{
				store.put(arr[i], store.getValue(arr[i]) + 1);
			}
			else
			{
				store.put(arr[i], 1);
			}
			i += 1;
		}
		print(" Result : ");
		print(" " + (store.count()));
		// Count distinct elements in another window
		i = size;
		while (i < n)
		{
			if (store.getValue(arr[i - size]) == 1)
			{
				// Need to remove element
				// When it occurs only once
				store.remove(arr[i - size]);
			}
			else
			{
				// Reduce element frequency
				store.put(arr[i - size], store.getValue(arr[i - size]) - 1);
			}
			if (store.containsKey(arr[i]))
			{
				// Increase element frequency
				store.put(arr[i], store.getValue(arr[i]) + 1);
			}
			else
			{
				// Add new element
				store.put(arr[i], 1);
			}
			print("  " + (store.count()));
			i += 1;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	var task: DistinctCount = DistinctCount();
	// Define array of integer elements
	var arr: Array < Int > = arrayOf(7, 2, 7, 2, 1, 4, 5, 1, 6, 4, 3, 3, 5, 5, 5);
	// Get number of element
	var n: Int = arr.count();
	var size: Int = 5;
	task.countDistinctWindow(arr, n, size);
}

Output

 Array :  7  2  7  2  1  4  5  1  6  4  3  3  5  5  5
 Result :  3  4  5  4  4  4  5  4  4  3  2
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment