Create Hacking_Cypher.cpp

[rohitkumar9710]

Issue Id you have worked upon -

402

Briefly explain your program logic -

The problem has used a very simple yet elegant application of math and number theory. The question demands you to cut an integer string in two non zero parts such that both are divisible by two given numbers a and b.

But since this string is too large, one cannot simply cut the string into two parts, and convert both of them into integers. We don't have any data structure to be able to handle those big numbers. Therefore, we create a prefix and a suffix array which would store in it the (prefix of length i) modulo a and (suffix of length n-i) modulo b respectively for every i in the range [1,n-1]. So, here we iterate through the string and pre calculate both the arrays.

Now, we simply traverse through the string and see if at any position the prefix and suffix both store 0, that is both are divisible by a and b respectively, and the suffix doesn't contains a zero in front. If we do find such a position, we print the results else a NO.

Time Complexity : O(Size of the string)

Screenshots(Attach 2 screenshots of your own input and output) -

Checklist:

Eg - If your code follow the below guidelines. Kindly change [] to [x]

All the conditions should be fulfilled for considering your code for merging -

• [X] I have mentioned the question as comment in my solution file.
  

• [X] My code follows the guidelines of this project.
  

• [X] I have performed a self-review of my own code.
  

• [X] I have commented my code.
  

• [X] My code gives the correct output.
  

• [X] I confirm that I have not copied the code from anywhere. In case its found that I have copied even after successful merge then I can be banned from the repository and hacktoberfest.
  

• [X] I affirm that I strictly follow contributing guidelines and code of conduct.

[rohitkumar9710]

@SarthakKeshari Done. Thanks.