leetCode Question: Additive Number

Additive Number

Additive number is a string whose digits can form 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.

For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

Analysis
For this question, the first thing we could handle is

  • How to determine the sum of two strings in int is equal to the other string in int?

I use the string manipulation to handle the case when the number is too larger to be stored in an long long type (in cpp). This is implemented in the checkEQ function shown in my code below. Note that, the question is not allowed to use "03", "02", ect format, we also have to eliminte such cases (by the if condition in Line 6 below). In my implementation, the swap operation is to make the longer number always stores in a. The Line 5 is to ignore the check if the two numbers a and c are totally different, regarding to the fact that the sum of two numbers will not exceede the max length of two numbers + 1.
E.g., a = 998, b = 80, c = a + b = 998 + 80 = 1078
The length of c will never be greater than length of a + 1, since the carry will never greater than 1. Using this properties of sum operation, we could easily implement the following code for checking the sum of three strings as shown in checkEQ function. DO NOT forget to check the last carry!

Next we are facing the main part of the problem: find a way to check the whole string. I will show how I handle this in a clear way (which may not be optimal but quite easy to understand).

From the problem we know that:

  • The length of each number could be different.
  • At least we should have 3 numbers, which forms the whole string.
  • If we find one match (a + b = c), we shall keep searching (b + c = ???)
  • If our search goes to the end of the number, we could return True.

These observations tell us that:

  • We could check each possible length of each number
  • The max length of first number is length of string - 2, the max length of second number is length of string - length of 1st number - 1.
  • We could use a recursion to do this search, since every time, the procedure is almost same, but the input data are different.
  • The termination condition of our recursion is whether we match the whole string.

Given these infomation, we could implement our recursion function, which is shown in my code below:

Code (C++):

class Solution {
public:
bool checkEQ(string a, string b, string c){
if (a.size() < b.size()){ a.swap(b); }
if (c.size()- a.size() > 2){ return false;}
if ((a[0] == '0' && a.size()>1)|| (b[0]=='0'&&b.size()>1)){return false;}
int i = a.size()-1;
int j = b.size()-1;
string s ="";
int carry = 0;
while (j>=0){
int tmp = ( int(a[i]-char('0')) + int(b[j]-char('0')) + carry );
s.insert(0, 1,char(tmp % 10 + '0'));
carry = tmp / 10;
i--;
j--;
}
while (i>=0){
int tmp = (int(a[i]-char('0')) + carry );
s.insert(0,1,char(tmp % 10 + '0'));
carry = tmp / 10;
i--;
}
if (carry > 0){ s = "1" + s; };
return s.compare(c)==0;
}
void search(string prev1, string prev2, string num, bool& res){
if (res == true){ return; }
if (num == ""){
res = true;
}else{
int sz = num.size();
if (prev1 == ""){
for (int i=1;i<=sz-2;i++){
prev1 = num.substr(0, i);
search(prev1, prev2, num.substr(i),res);
}
}
if (prev2 == ""){
for (int i=1;i<=sz-1;i++){
prev2 = num.substr(0, i);
search(prev1, prev2, num.substr(i),res);
}
}
for (int i=1;i<=sz;i++){
if (checkEQ(prev1, prev2, num.substr(0,i))==true){
search(prev2, num.substr(0,i), num.substr(i),res);
}
}
}
}
bool isAdditiveNumber(string num) {
string prev1 = "";
string prev2 = "";
bool res = false;
search(prev1, prev2, num, res);
return res;
}
};

Code(Python):

class Solution(object):
def checkEQ(self, a, b, c):
if a == "" or b == "":
return False
if a[0] == '0' and len(a) > 1 or b[0] == '0' and len(b) > 1:
return False
if len(a) < len(b):
a, b = b, a
if len(c) - len(a) > 2:
return False
i = len(a)-1
j = len(b)-1
s = ""
carry = 0
while j >=0:
tmp = int(a[i]) + int(b[j]) + carry
s = str(tmp%10) + s
carry = tmp / 10
i -= 1
j -= 1
while i >=0:
tmp = int(a[i]) + carry
s = str(tmp%10) + s
carry = tmp / 10
i -= 1
if carry == 1 :
s = "1" + s
return s == c
def search(self, prev1, prev2, num, res):
if res[0]:
return
if num == "":
res[0] = True
else:
if prev1 == "":
for i in xrange(1, len(num)-1):
self.search(num[0:i], prev2, num[i::], res)
elif prev2 == "":
for i in xrange(1, len(num)):
self.search(prev1, num[0:i], num[i::], res)
else:
for i in xrange(1, len(num)+1):
if self.checkEQ(prev1, prev2, num[0:i]):
self.search(prev2, num[0:i], num[i::], res)
def isAdditiveNumber(self, num):
"""
:type num: str
:rtype: bool
"""
prev1 = ""
prev2 = ""
current = ""
if len(num) < 3:
return False
res = [False]
self.search(prev1, prev2, num, res)
return res[0]

55 comments:

  1. CodingHoliday Camps - We provide the best online learning coaching for Stem Education Coding in Singapore. Get the best online Stem Education Coding for your kids.

    ReplyDelete
  2. Best Article BUY ADDERALL ONLINE Excellent post. I appreciate this site. Stick with it! Because the admin of this web page is working, no doubt very quickly it will be well-known, due to its quality contents.This website was how do you say it? Relevant!! Finally, I’ve found something that helped me.

    ReplyDelete

  3. Thanks for Valuable Information man, IT was Really helpful for me.

    Also, Please reach me for all types of loans - Personal loan at low interest rate in Bangalore

    Trust me Its Really Worth trying for Certified mobile service center in Marathahalli

    ReplyDelete

  4. Best content.Thank you so much for sharing,i have learnt something new.I hope you will share more information like this,keep updating.
    Best Data Science Certification Course in Bangalore

    ReplyDelete
  5. dank vapes are the best brand of vape cartridges in the market. These dank vapes cartridges have however suffered a backlash in the recent weeks with multiple reports on how these dank vapes carts cause cancer and other related lung disease.
    dank vapes cart however remain one of the best cartridges. dank vapes are sold in multiple states over the USA. dank vapes cart compost one of the black markets finest vape products. But this backlash has caused a fall in the consumption of the vape by adults.The 710 Kingpen brand is also on the rise in market demands as well as skywalker OG products.
    Recently juul pods also faced a similar backlash. juul starter kits have also fallen in market demand. mango juul pods are refillable juul pods and can be gotten as juul pods bulk. juul skins and juul accessories all come with the juul kits.
    buy juul online at cheap prices buy cocaine online
    buy Keytruda online and other cancer medications such as buy avastin online , buy Herceptin online

    ReplyDelete
  6. Thanks for sharing such informative peice of work ,Welcome to Glock Store ,a Discreet online depot where you can buy firearms and ammunition , Buy guns online ,
    buy ammo discreetly without monotonous deocumentations and ship to your prefered location with no hassle.We are FFL Dealers and stricktly follow the Regulations of the Gun Control Act(GCA).Purchasing Fireamrs and Ammunition online with caution has always been a long process of paperwork because of the inter/Intra state Laws controlling the buying and distribution.At Glock store online shop we cut the Gordian knot and deliver to your location with no hassle.We have a wide range of firearms and ammunition for sale ,buy Ammo such as shotguns,Long guns,Magazines, Optics and accesories which include Century Arms,Kel-Tec,
    Ruger,
    AR15,
    AK47,.Despite the perusal increase in surounding firearms,we issue uncomplicated paths to acquire Firearms for individual and or Family security.If you have ever asked yourself
    how to buy guns and ammunition online with ease and,safety then your question is answered once you are here.All you have to do is choose your firearms, optic, magazine,accessories and add to cart then proceed to check out. READ MORE on how to buy guns and ammunition online discreet.
    Pain management, pain medicine,buy pain medication and buy research chemicals, pain control or algiatry, is a branch of medicine employing an interdisciplinary approach for easing the suffering and improving the quality of life of those living with chronic pain,
    buy lipitor
    You can also buy weed online, buy cbd oil

    ReplyDelete
  7. hanks for sharing such informative peice of work ,Welcome to our for Pinball machines ,At pinball machine for sale, we love fixing, customizing and selling all types pinball machine and have been doing it for over 20 years. With all the innovation and new pinball companies starting up, it’s great that we’re in the epicenter of pinball world, Chicago, buy high quality japanese used car tyres. Pinball machine manufacturers have been forming in Chicago from the earliest days of pinball. That’s probably why we’re able to find great vintage pinballs tor refurbish! Buy pinball machines online such as antique pinball machine,refurbished pinball machines ,stern pinball machine and many more.
    s

    ReplyDelete
  8. Order our JUUL Pods and JUUL devices today and become a part of the healthier and safer smoking family.

    Alpine Berry Flavor
    JUUL devices
    Mango Nectar

    ReplyDelete

  9. Thanks for sharing such informative peice of work ,Welcome to Glock Store ,a Discreet online depot where you can buy firearms and ammunition , Buy guns online ,
    buy ammo discreetly without monotonous deocumentations and ship to your prefered location with no hassle.We are FFL Dealers and stricktly follow the Regulations of the Gun Control Act(GCA).Purchasing Fireamrs and Ammunition online with caution has always been a long process of paperwork because of the inter/Intra state Laws controlling the buying and distribution.At Glock store online shop we cut the Gordian knot and deliver to your location with no hassle.We have a wide range of firearms and ammunition for sale ,buy Ammo such as shotguns,Long guns,Magazines, Optics and accesories which include Century Arms,Kel-Tec,
    Ruger,
    AR15,
    AK47,.Despite the perusal increase in surounding firearms,we issue uncomplicated paths to acquire Firearms for individual and or Family security.If you have ever asked yourself
    how to buy guns and ammunition online with ease and,safety then your question is answered once you are here.All you have to do is choose your firearms, optic, magazine,accessories and add to cart then proceed to check out. READ MORE on how to buy guns and ammunition online discreet.
    Pain management, pain medicine,buy weed strains online and buy research chemicals, pain control or algiatry, is a branch of medicine employing an interdisciplinary approach for easing the suffering and improving the quality of life of those living with chronic pain,
    buy lipitor
    You can also buy weed online, buy cbd oil

    ReplyDelete




  10. Coding


    Holiday Camps - Have fun with bricks while learning at the same time! Bricks 4 Kidz offers the best STEM and Coding Enrichment platform for your child. Join us now!



    https://www.bricks4kidz.com.sg/about-us/

    ReplyDelete
  11. medical care is what many people lack in the interior areas of the world. people face a lot of health issues everyday without solution. buy psychedelics online, Buy weed online, Buy cocaine online

    ReplyDelete

  12. buy weed online at Legit Weed Store

    order your cannabis now at Order Cannabis Meds

    Buy marijuana online at 420 Delivery Store

    Buy medical cannabis online at at Canna Med Shop

    Get your Pill refills at Pill Pharma

    ReplyDelete
  13. Tack Köp legit piller online i sverige på Mundi Apotek

    Tack Köp legit piller online i sverige på   Scandinavia Apotek

    Tack Köp legit piller online i sverige på    battrehalsa-apotek 

    ReplyDelete
  14. Thankѕ for another informative website. Where else may I get that type of information written in such an ideal means? Ӏ have a miѕsion that I'm just now working on, and I've been at the glance out for such info.
    CZ P-01 9mm

    ReplyDelete
  15. https://k2incenseonlineheadshop.com/
    info@k2incenseonlineheadshop.com
    k2incenseonlineheadshop Buy liquid incense cheap Buy liquid incense cheap For Sale At The Best Incense Online Shop

    ReplyDelete
  16. Buy K2 Liquid Online With Fast And Secured Delivery At Your Doorsteps.

    What are your views about light-weight cbd packaging that are easy to carry and handy packaging solution? Well, OXO Packaging structures the most stylish and innovative series of custom window boxes that will quickly grabs the customer attention on the retail shelves.

    Contact us:+1(213)3421053 Email: service@cbdwarehousestore.com

    ReplyDelete
  17. Buy California Driver’s License, license renewal online ca - US Driver’s License


    Here at Buy Documentation, you can buy fake documents at a fraction of a cost. We keep our prices low to meet the needs of all our customers.

    Buydocumentaion.com, We provide Best Quality Novelty Real and Fake IDs and Passport, Marriage Certificates and Drivers license online.

    https://buydocumentation.com/document/fake-covid-test-buy-covid-19-test-results-online/

    https://buydocumentation.com/buy-real-drivers-license/

    https://buydocumentation.com/buy-real-id-cards/

    https://buydocumentation.com/canada-visa/

    https://buydocumentation.com/

    ReplyDelete

  18. https://liquidincenseshop.com/ sales@liquidincenseshop.com
    Buy liquid incense cheap ,Incense for sale online offers ,Liquid Spice ,k2 chemical spray for sale , where to buy k2 near me ,K2 E-LIQUID. liquid k2 , k2 spice spray ,herbal incense for sale , Liquid Herbal Incense, cheap herbal incense , strong herbal incense for sale , Liquid k2 on paper , Liquid K2 , Legal High Incense , liquid herbal incense for sale, Order Strong Liquid Incense , Herbal Incense For Sale , Buy Vape Cartridges , Cheap K2 Spice , Legal Potpourri , Buy Herbal Incense Discrete , Legit Herbal Incense Website , Liquid Incense Overnight Delivery , Buy Potpourri With Credit Cards , buy herbal incense with debit card, , Where To Order Liquid Incense Online , Buy Liquid Incense With Bitcoin , Buy K2 Liquid Incense On Paper In USA , Strongest Incense In USA

    https://k2incenseonlineheadshop.com/ sales@k2incenseonlineheadshop.com
    Buy liquid incense cheap ,Incense for sale online offers ,Liquid Spice ,k2 chemical spray for sale , where to buy k2 near me ,K2 E-LIQUID. liquid k2 , k2 spice spray ,herbal incense for sale , Liquid Herbal Incense, cheap herbal incense , strong herbal incense for sale , Liquid k2 on paper , Liquid K2 , Legal High Incense , liquid herbal incense for sale, Order Strong Liquid Incense , Herbal Incense For Sale , Buy Vape Cartridges , Cheap K2 Spice , Legal Potpourri , Buy Herbal Incense Discrete , Legit Herbal Incense Website , Liquid Incense Overnight Delivery , Buy Potpourri With Credit Cards , buy herbal incense with debit card, , Where To Order Liquid Incense Online , Buy Liquid Incense With Bitcoin , Buy K2 Liquid Incense On Paper In USA , Strongest Incense In USA

    https://k2incenceshop.com/ sales@k2incenceshop.com
    Buy liquid incense cheap ,Incense for sale online offers ,Liquid Spice ,k2 chemical spray for sale , where to buy k2 near me ,K2 E-LIQUID. liquid k2 , k2 spice spray ,herbal incense for sale , Liquid Herbal Incense, cheap herbal incense , strong herbal incense for sale , Liquid k2 on paper , Liquid K2 , Legal High Incense , liquid herbal incense for sale, Order Strong Liquid Incense , Herbal Incense For Sale , Buy Vape Cartridges , Cheap K2 Spice , Legal Potpourri , Buy Herbal Incense Discrete , Legit Herbal Incense Website , Liquid Incense Overnight Delivery , Buy Potpourri With Credit Cards , buy herbal incense with debit card, , Where To Order Liquid Incense Online , Buy Liquid Incense With Bitcoin , Buy K2 Liquid Incense On Paper In USA , Strongest Incense In USA

    ReplyDelete
  19. This blog looks just like my old one! It's оn a totally different subject but it has pretty much the same layout and design. Great choice of colours!
    Dirty Harry Pinball Machine

    ReplyDelete
  20. Nice blog!
    Buy Liberty caps mushroom Online.
    The effects of magic mushrooms usually begin in 30 minutes when eaten, or within 5–10 minutes when taken as a soup or tea, and can last for approximately 4–6 hours.

    ReplyDelete

  21. CANNABIS DISPENSARY GOALS


    We are the most legit cannabis dispensary with both wholesale and retail weed for sale. Marijuana extract and thc cartridges are also available. We deliver in almost all states in the US and Puerto Rico. We are available in Canada, UK, USA, South America, Europe and Australia

    Buy Krt Carts Online

    Buy Pluto Strain Online

    Buy Sweet Tea Online 

    Buy White Runtz Sungrown Online

    Buy Banana Kush Online 

    Buy Bubbleberry Strain Online

    Buy Pink Panther Online

    Buy White Runtz 

    Packwoods x gashouse Tear gas

    https://cookieswood.com/shop/

     

    ReplyDelete
  22. Savannah cats & Bengal cats & Serval cats for sale
    We have bengal and savannah kittens available and ready for new homes. Our cattery have been under

    existence for over 12 year now and we can proudly say all kittens and cats at our breeding home have

    been well trained, socialized with other pets and kids and also very healthy making them good fit for

    you and your family.
    https://savannahbengal.company.com

    bengal kittens for sale | Bengal cats for sale | savannah kittens for sale | savannah cats for sale |

    bengal kittens | savannah cats | savannah kittens | savannah kittens for sale near me | bengal kittens

    for sale near me | savannah kitten for sale | bengal kitten for sale|Bengal cat for sale| Savannah cat

    for sale| Serval cat for sale | Serval kitten for sale,savannah kittens for sale, serval cat for sale,

    savannah cat for sale, savannah cats for sale, f1 savannah cat for sale, serval cat for sale, exotic

    cats for sale, f1 savannah cat, f4 savannah cat, cats for sale, savannah cats, Serval kittens for sale,

    savannah kittens for sale near me, savannah cats for sale near me, bengal kittens for sale, bengal

    kittens for sale near me.

    ReplyDelete
  23. Firearms, guns for sale online


    We offer guns for sale for sale, firearms for sale guns for sale near me, guns for sale, cheap gun safes for sale, used guns for sale, guns for sale near me,3d printed guns for sale,, and Cheap Guns for sale at affordable prices. We also provide secure payment processors as well as discreet and swift delivery to any part of the world. Mail Order Guns from the most trusted Gun shop near me and which you can get a gun fire arms at Gun Me Plug

    For most of the weapons available to the general public, this is indeed the case.
    However, it is not so easy to safely fire a pistol and hit what you are aiming at.
    Not to mention the maintenance of the weapon, its safe storage, the purchase of suitable ammunition, etc.
    A certain degree of training is absolutely necessary for this, and anyone who buys a gun is simply obliged to Learn to shoot and not undergo safety training.


    https://www.gunmeplug.com/




    Order Ruger firearms online


    ruger rifles for sale online


    ruger online catalog


    ruger firearms sales online


    ruger 20% off couponruger new owner special offerruger firearms rebate offersruger discounts and rebatesruger firearms website




    ruger lcr 9mm revolver price


    ruger lcr 22lr for sale


    ruger lcr 38 best price


    ruger lcp 22 for sale


    https://www.gunmeplug.com/


    ruger lcr 22lr cost


    ruger 45 caliber handgun


    ruger american 45 cal

    ReplyDelete
  24. Hempgrade.co.uk is one of the most promising
    CBD flower wholesalers on the market. Our wholesalers in Europe
    Can receive our product while still earning a profit because Europe is priced lower.
    All of our strains are lab tested to have less than 0.2 percent THC,
    And they are produced by a strict professional staff with years of experience in providing the greatest CBD quality.
    We are a Premium Hemp Flowers Wholesaler. We are a European hemp flower wholesaler.
    https://hempgrade.co.uk/
    cbn isolate uk
    cbd hash 1kg uk
    strong cbd flower uk
    cbd hash 1kg
    cbd hash uk cheapest
    cbd flower for sale uk
    hemp buds uk
    dutch delight strain
    buy cbd jelly hash online uk
    high cbd nepal cream uk
    cbd flower wholesale europe
    cbd flower europe
    top shelf cbd flower uk
    cbd flowers wholesale europe
    cbd flower wholesale uk
    cbd hash uk cheapest
    buy cbd flower online
    cbd hemp flowers for sale
    hemp flower europe
    cbd buds europE
    cheap cbd flower uk
    cheap cbd flower pounds
    cbd flower for sale uk
    cbd flower online uk
    cbd flowers europe
    wholesale cbd flower europe
    cbd flower europe wholesale
    https://hemptradesupply.com/
    wholesale cbd flower
    wholesale hemp buds
    buy cbd buds uk
    buy hemp online
    cbd hemp buds uk
    wholesale hemp biomass
    hemp buds uk
    hemp buds wholesale
    hemp flowers uk
    buy hemp flower uk
    cbd buds uk
    wholesale cbd buds
    buy hemp flower wholesale
    cbn isolate uk
    cbd hash 1kg uk
    strong cbd flower uk
    cbd hash 1kg
    cbd hash uk cheapest
    cbd flower for sale uk
    hemp buds uk
    dutch delight strain
    buy cbd jelly hash online uk
    high cbd nepal cream uk
    buy hemp buds uk
    dutch delight strain review
    cbd flower wholesale uk
    buy wholesale cbd flower in uk
    dutch delight cbd hemp flower
    cbd hash online
    buy cbd hash uk
    bulk cbd flower wholesale
    cbd hash uk
    cbd hemp buds uk
    bulk cbd flower supplier uk
    wholesale cbd flower uk
    high cbd flower uk
    star master strain
    cbd hash for sale uk
    hemp flowers uk
    hemp flowers cherry wine uk
    best cbd hash uk
    dutch delight cbd
    jelly hash
    CBD flower for sale in bulk.
    we have premium CBD Hemp flower under 0.2%THC.
    We provide EU with premium CBD hemp flowers
    We Provide Wholesale CBD Flowers Throughout Europe.
    We have the best products at the best prices.
    smokable CBD hemp flowers,
    wholesale CBD hemp flowers,
    organic CBD ... CBD distillate,
    bulk CBD, white label CBD,
    private label CBD, CBD for food.
    Cbd hemp flower wholesale uk
    our products is here to create oil discount.
    Winterized extract mixed with premium,
    small-batch producers.
    Cbd wholesale europe / wholesale cbd flower uk.
    Switzerland cbd wholesale used in research needs to the aerial hemp flavor.
    Buy hemp flowers in bulk.
    swiss cbd buds uk
    import cbd flowers uk
    high strength cbd flower
    hemp biomass for sale uk
    wholesale legal buds
    swiss hemp flower wholesale
    wholesale organic hemp flower
    hemp hash uk
    cbd czech republic


    ReplyDelete
  25. Nice Blog! I really loved reading through this Blog... Thanks for sharing.......
    Awesome Blog thanks for share your valuable information

    Inwizards Technology - Internet of Things IoT

    iot development company
    hire iot developer

    ReplyDelete
  26. The world is moving towards unsafe climatic changes. Write For Us Telemarketing

    ReplyDelete
  27. What a great article, thank you for writing and sharing with us
    colourist logo

    ReplyDelete
  28. Great job for publishing such a beneficial web site. Reported calls

    ReplyDelete
  29. Best online slots at casino - Dr.MCD
    Discover 수원 출장마사지 the best slot machines and casino, 인천광역 출장안마 slots, and 서귀포 출장샵 bingo sites to play free games at today's best casinos. We 김포 출장마사지 list 제천 출장샵 10 casino sites and review

    ReplyDelete
  30. Bitcoin has progressed profoundly and is currently the field’s biggest cryptographic money through market capitalization.
    buy antminer b7 online

    Contact Us:+14064043039

    ReplyDelete
  31. Buy Crystal Mеth Online
    Buy Meth Online. Crystal mеth iѕ the common name fоr сrуѕtаl methamphetamine, a ѕtrоng аnd highly addictive drug that affects the central nеrvоuѕ ѕуѕtеm. meth for sale, buy meth, buy crystal meth online, buy methamphetamine online, crystal meth online, buy crystal meth, order meth online

    ReplyDelete
  32. Any animal can take a gander at the WiFi Password Hacker Online segment in the graph and might want to utilize it free of charge. Hack Wifi Password Online Android

    ReplyDelete
  33. Mega Downloader APK gives client controlled scrambled distributed storage space and talk from one side to another ordinary internet browsers, mutually with dedicated applications for portable methodology. Mega Download Link

    ReplyDelete

  34. This blog never ceases to amaze me, no matter how often I come.
    https://easyserialkeys.com/plagiarism-checker-x-crack/

    ReplyDelete