Leetcode Additive Number problem solution YASH PAL, 31 July 2024 In this Leetcode Additive, Number problem solution Additive number is a string whose digits can form an additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. we have given a string containing only digits ‘0’-‘9’, write a function to determine if it’s an additive number. Problem solution in Python. class Solution: def isAdditiveNumber(self, num: str) -> bool: def ableToSeeTheLight(n0, n1, num_str): s = str(n0+n1) #print("n0", n0, "n1", n1, "s", s, "num", num_str) if not num_str and num.endswith(str(n1)): return True if num_str.startswith(s): return ableToSeeTheLight(n1, int(s), num_str[len(s):]) else: return False for i in range(1, len(num)): if i > 1 and num[0] == '0': continue for j in range(i + 1, len(num)): if j - i > 1 and num[i] == '0': continue n0 = int(num[0:i]) n1 = int(num[i:j]) if ableToSeeTheLight(n0, n1, num[j:]): return True return False Problem solution in Java. class Solution { public boolean isAdditiveNumber(String num) { int n = num.length(); if (n < 3) return false; for (int i = 1; i <= n / 2; i++) { if (i > 1 && num.charAt(0) == '0') break; for (int j = i + 1; j < n; j++) { if (j > i + 1 && num.charAt(i) == '0') break; long first = Long.parseLong(num.substring(0, i)); long second = Long.parseLong(num.substring(i, j)); int k = j; while (k < n) { long target = first + second; String s = String.valueOf(target); if (k + s.length() <= n && num.substring(k, k + s.length()).equals(s)) { k += s.length(); first = second; second = target; } else break; } if (k == n) return true; } } return false; } } Problem solution in C++. class Solution { public: vector<long long> path; bool dfs(string& s, int start) { int sz = path.size(); if (start == s.length() && path.size() >= 3) { return true; } long long n = 0, max_len; max_len = (s[start] == '0' ? 1 : 15); for (int i = start; i < s.length() && max_len -- ; i++) { n = n * 10 + (s[i] - '0'); if (sz >= 2 && path[sz - 1] + path[sz - 2] < n) return false; else if (sz <= 1|| path[sz - 1] + path[sz - 2] == n) { path.push_back(n); if (dfs(s, i + 1)) return true; path.pop_back(); } } return false; } bool isAdditiveNumber(string& num) { return dfs(num, 0) ; } }; Problem solution in C. bool check(char* num, char* num1, char* num2, int last_idx){ int num1_len = strlen(num1), num2_len = strlen(num2); if(num1_len>1 && num1[0] == '0' || num2_len>1 && num2[0] == '0' || last_idx > strlen(num)-1) return false; long long n1 = strtol(num1,NULL,10); long long n2 = strtol(num2,NULL,10); long long sum = n1+n2; int sum_len = 0; while(sum>0){ sum_len+=1; sum/=10; } if(last_idx+sum_len>strlen(num)-1) return false; char* sum1 = (char*)calloc(sum_len+1,sizeof(char)); memcpy(sum1,num+last_idx+1,sizeof(char)*sum_len); sum1[sum_len] = ' '; sum = strtol(sum1,NULL,10); if(sum!=(n1+n2)) return false; if(last_idx+sum_len == strlen(num)-1) return true; if(sum_len == 0)// for "000" test case sum_len = 1; return check(num,num2,sum1,last_idx+sum_len); } bool isAdditiveNumber(char * num){ int len = strlen(num); for(int i=1;i<=len/2;i++){ char* num1 = (char*)calloc(i+1,sizeof(char)); memcpy(num1,num,sizeof(char)*i); num1[i] = ' '; for(int j=1;j<=(len-i)/2;j++){ char* num2 = (char*)calloc(j+1,sizeof(char)); memcpy(num2,num+i,sizeof(char)*j); num2[j] = ' '; if(check(num,num1,num2,i+j-1)) return true; } } return false; } coding problems