Matrix Problems

Comments

Post a Comment

Popular posts from this blog

Print all subsets of given size of a set

Generate all possible subset of size  r  of given array with distinct elements. Examples: Input : arr[] = {1, 2, 3, 4} r = 2 Output : 1 2 1 3 1 4 2 3 2 4 3 4 Input : arr[] = {10, 20, 30, 40, 50} r = 3 Output : 10 20 30 10 20 40 10 20 50 10 30 40 10 30 50 10 40 50 20 30 40 20 30 50 20 40 50 30 40 50 The idea here is similar to  Subset Sum Problem . We one by one consider every element of input array, and recur for two cases: 1) The element is included in current combination (We put the element in data[] and increment next available index in data[]) 2) The element is excluded in current combination (We do not put the element and do not change index) When number of elements in data[] become equal to r (size of a combination), we print it. This method is mainly based on  Pascal’s Identity , i...
Read more

[GE][First Method]Find smallest permutation of given number

Smallest number by rearranging digits of a given number Find the Smallest number (Not leading Zeros) which can be obtained by rearranging the digits of given number. Examples: Input: n = 846903 Output: 304689 Input: n = 55010 Output: 10055 Steps to find the smallest number. Count the frequency of each digit in the number. Place the smallest digit (except 0) at the left most of required number. and decrement the frequency of that digit by 1. Place all remaining digits in ascending order from left to right. This solution is based on  counting sort . // C++ program for finding smallest number // from digits of given number #include<iostream> using namespace std;     // function to find the smallest number int smallest( int num) {      // initialize frequency of each digit to Zero      int freq[10] = {0};          // count frequency of e...
Read more

[23] Find top k (or most frequent) numbers in a stream

Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (According to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all distinct elements sorted by frequency. Examples: Input :  arr[] = {5, 2, 1, 3, 2}              k = 4 Output : 5 2 5 1 2 5 1 2 3 5 2 1 3 5 Input  : arr[] = {5, 2, 1, 3, 4}              k = 4 Output : 5 2 5 1 2 5 1 2 3 5 1 2 3 4 Expected time complexity is O(n * k) Given an array of n numbers. Your task is to read numbers from the array and keep at-most K numbers at the top (According to their decreasing frequency) every time a new number is read. We basically need to print top k numbers sorted by frequency when input stream has included k distinct elements, else need to print all...
Read more