{ Programming }

Given a non-negative integer c , your task is to decide whether there're two integers a and b such that a 2 + b 2 = c. Example 1: Input: 5 Output: true Explanation:1 2 + 2 2 = 5 Example 2: Input: 3 Output: false Source: LeetCode Solution in C++ The idea is simple: Instead of looking for all possible combinations of a and b. Iterate from 0 to sqrt(c), check if the result of c - a 2 is a perfect square, if so, we have found the combinations of sum of squares (a 2 + b 2 = c).   class Solution { public: bool judgeSquareSum(int c) { for(int i=0;i<=(int)sqrt(c);++i) if(is_perfect_square(c-i*i)) //check is the number is perfect square return true; return false; } bool is_perfect_square (int num){ int sq = sqrt(num); return sq*sq == num; } };

Given an input string, write a regular recursive function that returns the decoded (uncompresseed form) Run Length Encoded   (is a simple form of data compression where repeated character are replaced by count followed by the character repeated) string for the input string. Below are some examples: decode("*") =>* decode("3+") =>+++ decode("11*") =>*********** decode("101+") =>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ decode("abcde10+10*10+10x") =>abcde++++++++++**********++++++++++xxxxxxxxxx decode("\\") =>\ decode("\1\2\3") =>123 decode("13\7x") =>7777777777777x decode("5\\") =>\\\\\ decode("4\12\23\3") =>111122333 decode("4\\2\3") =>\\\\33 NOTE: To represent a single backslash, it’s necessary to place double backslashes (\\) in the input string to obtain the desired in

Problem Statment: Write a recursive function to compare two cstrings.  Similiar to the strcmp() function return an integer greater than, equal to, or less than zero, accordingly as the string pointed to by s1 is greater than, equal to, or less than the string pointed to by s2. "-1" if the first character that does not match has a  lower value in s1 than in s2 "0"    the contents of both strings are equal  "1"    the first character that does not match has a greater value in s1 than in s2  int str_cmp ( char const * s1 , char const * s2 ) { if ( * s1 = = '\0' & & * s2 = = '\0' ) //if both character are null character return 0 ; //they must be equal if ( * s1 > * s2 ) return 1 ; if ( * s1 < * s2 ) return - 1 ; return str_cmp ( s1 + 1 , s2 + 1 ) ; }

Problem Statment: Write a recursive function to reverse a string. Write a recursiveunction to reverse the words in a string, i.e., "cat is running" becomes "running is cat".   #include<iostream>       void reverse ( char * begin , char * end ) { if ( begin > end ) return ; else { char temp = * begin ; * begin = * end ; * end = temp ; reverse ( begin + 1 , end - 1 ) ; } } void reverse_word ( char * start , char * begin , char * end ) { if ( * end = = '\0' ) { reverse ( begin , end - 1 ) ; begin = end + 1 ; reverse ( start , end - 1 ) ; //reverse after all words are reversed return ; } if ( * end = = ' ' ) { reverse ( begin , end - 1 ) ; begin = end + 1 ; } reverse_word ( start , begin , end + 1 ) ; } int main ( void ) { char s1 [ ] = " cat is running " ; reverse_word ( s1 , s1 , s1 ) ; std :

Problem Statment: Write a (regular or tail) recursive function that converts a valid hexadecimal string into a decimal value no longer than 64 bits.   "0x0"  => 0   "0x1"  => 1  "0xABCD" => 43981   int charTodec ( char const ch ) { if ( ch > = 'a' & & ch < = 'f' ) return ch - 'a' + 10 ; if ( ch > = 'A' & & ch < = 'F' ) return ch - 'A' + 10 ; else return ch - '0' ; } unsigned long long int hexTodec ( char const * str , unsigned long long result ) { if ( * str = = '\0' ) return result ; else { result = result * 16 + charTodec ( * str ) ; return hexTodec ( str + 1 , result ) ; } }

# include < iostream > bool is_in_array ( int * begin , int * end , int target ) { int mid = ( end - begin ) / 2 ; if ( * begin > target | | * end < target ) //value has to be between [begin,end] return false ; // to continue if ( begin [ mid ] = = target ) return true ; if ( begin [ mid ] > target ) //look at the left subarray return is_in_array ( begin , begin + mid - 1 , target ) ; // (begin[mid] < target) look at the right subarray return is_in_array ( begin + mid + 1 , end , target ) ; } bool find_in_array ( int arr [ ] , int target , int size ) { int * begin = arr ; int * end = begin + size - 1 ; bool result = is_in_array ( begin , end , target ) ; return result ; } void test_is_in_array ( bool expected , int arr [ ] , int target , int size ) { bool result = find_in_array ( arr , target , size ) ; std :: cout