"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!! Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc. Team Cracking The Code
u will be given pairs.. u need to see whether they have any gaps..u can think pairs are like intervals..
ex1: max no:20 pairs: 11-15, 0-5, 18-20, 14-19, 6-13
the above has no gaps..because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)
#include < iostream>#include < algorithm>#include < time.h>using namespace std; // Swap functiontemplate < class T>void swap(T *i, T *j){ T temp = *i; *i = *j; *j = temp;} // function to reverse a range of valuestemplate < class T>void reverse(T *start, T *end){ while(start < end) { swap(start,end); start++; end--; }}// array_end does not point to a valid element of the array// it is beyond the last elementtemplate < class T>bool permute(T* array_start,T* array_end){ // array does not contain any element if(array_start == array_end) return false; // array contains only 1 element if(array_start+1 == array_end) return false; T *i,*i1,*j; // Make the pointers point to last and the second last elements i = array_end - 2; i1 = array_end - 1; // find two elements a,b such that a < b and index of a // is less than the index of b while(true) { // If such a pair is found, find an element c such that // c > a, then swap them and reverse the list from b till // the end if(*i < *i1) { j = array_end -1; // worst case is that j == i1 while(!(*i < *j)) j--; // This step implements the lexicographic order by // bringing the larger element in the front swap(i,j); // Reverse the list so that we have a weak decreasing // order in the remainder of the list reverse(i1,array_end-1); return true; } // Now the list is in strictly decreasing order // no more permutations are possible, return the // list as it was originally received if(i == array_start) { reverse(array_start,array_end-1); return false; } // decrement the two pointers i--; i1--; } }template< class T>void display(T *array,T *end){ T* i = array; while(i < end) { cout << *i << "-"; i++; } cout << endl;} int main(){ srand(time(NULL)); // You can declare any type here of any size int size = 4; char array[size]; cout << "Enter four numbers" << endl; for(int i=0;i < size;i++) cin>>array[i]; // C++ sort function so that the permutation // function receives the elements in the sorted order // in order to create a lexicographic order sort(array,array+4); // First permutation display(array,array+4); int count=1; // Call the function while you get valid permutations while(permute(array,array+4)) { count++; display(array,array+4); } cout << "Total permutations are " << count << endl; system("pause"); return 0;}
