Basic Data structure questions

Comments

Post a Comment

Popular posts from this blog

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Subset Sum Problem | DP-25 Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. Example: Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9 Output:  True  //There is a subset (4, 5) with sum 9. // A recursive solution for subset sum problem #include <stdio.h>     // Returns true if there is a subset of set[] with sun equal to given sum bool isSubsetSum( int set[], int n, int sum) {     // Base Cases     if (sum == 0)       return true ;     if (n == 0 && sum != 0)       return false ;         // If last element is greater than sum, then ignore it     if (set[n-1] > sum)       return isSubsetSum(set, n-1, sum);         /* else, check if sum...
Read more

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