How to proof the COUNT is always less than 10?


  • 14
    I

    At first, I solved this problem with the considering of the cases when COUNT is greater than 9, which can not be handled using:curString +=count+'0';, since it is more than one digit. And I solved it using itoa. But when I thinked about the problem, it seems that the COUNT is always less than 10, even 4. Then I re-writed the solution and also accepted by OJ.

    Can you guys help me proof it?
    My code:

    class Solution {
    public:
        string countAndSay(int n) {
    		string prevString;
    		string curString = "1";
    		for (int i = 1; i<n; ++i){
    			prevString = curString;
    			curString = "";
    			int count = 1;
    			char digit = prevString[0];
    			for (int j = 1; j<prevString.length(); ++j){
    				if (prevString[j] == digit){
    					++count;
    				}
    				else{
    					
    					curString +=count+'0'; //myItoa(count);
    					curString += digit;
    					digit = prevString[j];
    					count = 1;
    				}
    			}
    			curString += count+'0';//myItoa(count);
    			curString += digit;
    		}
    		return curString;
        }
    /*private:
    	string myItoa(int i){
    		string str;
    		while (i){
    			str += i%10+'0';
    			i /=10;
    		}
    		reverse(str.begin(), str.end());
    		return str;
    	}*/
    };

  • 30
    M

    Proof by exhaustion and contrapositive:

    In order for a number greater than 4 to be created, there must be a series of numbers n>4 in length all the same digit. Therefore, there is a subset of that series where the count would only reach 4. Because of this, any proof for the existence of a chain resulting in a number greater than 4 is also a proof for the existence of a 4-chain. Using the proof by contrapositive, this means that if 4-chains are proved to be impossible, then any n-chain with n>4 is also impossible.

    In order to start with a chain with numbers greater than 4, you must assume that a 4-chain is possible in the first place, which is circular reasoning, and so cannot be used as an initial point. It is further impossible to have a negative value, since the counting numbers do not include them.

    Therefore, the only chains able to create a 4 (at least the first one) are 0000, 1111, 2222, or 3333.

    0 0 0 0 -> 40
    

    The 0000 is read zero 0, zero 0, which must come from . Since there is nothing present, it could in theory occur anywhere in the string. However, since they would be next to each other, if the 0 is repeated as would be neccessary, the zeros would add together, resulting in just zero 0, leaving only 20, not 40.

    1 1 1 1 -> 41
    

    The 1111 is read one 1, one 1 (or 11), which translates to 21, not 1111. This contradicts the assumption that there is a way to get 1111, and so prevents 4 or greater from appearing. Therefore, 1s cannot reach 4.

    2 2 2 2 -> 42
    

    The 2222 is read two 2, two 2 (or 22 22), which is identical to the output. Since the input maps to itself, there is no way to leave that cycle, or it already would have. If 2222 exists in the input, then 2222 must have mapped to it. It cannot reach 42. Therefore, 2s cannot reach 4.

    3 3 3 3 -> 43
    

    The 3333 is read three 3, three 3 (or 333 333). This in turn would require 333 333 333. This fails in two respects. First, that the previous inputs would not merge to 63 or 93. The second, that the sequence eventually traces back to the origin, 1. Since it keeps increasing in length as the number of rounds since the start decreases, it cannot have started at 1. Therefore, 3s cannot reach 4.

    As every possible case has been examined, and none can reach a 4 while starting at the given beginning (1), it is not possible for a 4-chain to occur, meaning a 4 cannot appear in any valid string for this problem. Further, as stated above, since a 4-chain is impossible, so too are all n-chains with n>4, so no number greater than 4 can appear either.


  • -1
    D

    Do we ever need to prove anything to code this? Just curious, as I found it almost the most straightforward problem to code in the OJ so far. But wondering whether my answer just passed OJ with any hidden bug?

    Thanks

      string countAndSay(int n) {
            string previous;
            if (n==0)
            return previous;
             previous = "1";
            if (n==1)
            return previous;
            string cur;
            for (int i=1;i<n;i++)
            {
                int j=previous.size();
                for (int k=0;k<j;k++)
                {
                    int c=1;
                    if (k+1<j)
                    {
                    while(previous[k]==previous[k+1]&&k+1<j)
                    {
                        c++;
                        k++;
                    }
                    
                    }
                    
                    cur += to_string(c)+previous[k];
                }
                previous = cur;
                cur.clear();
            }
            return previous;
        }

  • 2
    W

    1111 doesn't necessarily read one 1, one 1. It could be '? 1s, one 1, one ?' It still contradicts, though.


  • 0
    A

    Whats the use of previous and current PLease explain. The problem appears tougher to me


  • 0
    N

    It's like a compression algorithm.


  • 0
    J

    In order for a number greater than 4 to be created, there must be a series of numbers n>4 in length all the same digit. Therefore, there is a subset of that series where the count would only reach 4.

    But how can you say a subset is usable to reach 4? e.g. …11111… -> 51, only when you start counting from (maybe) the second 1 can you reach 4.


  • 0
    M

    By subset of the series, I meant that a given pattern, like 11111, as you said, could have multiple 1s in a row. However, to build such a pattern, you need one 1, one 1, one x or x 1s, one 1, one 1. Either way, for that pattern to exist, the pattern for one 1, one 1 must be valid. This would be 1111, or 4 ones, meaning that a 5 length chain requires that a 4-length chain be possible. It does not guarantee that a 5 chain is possible if a 4 chain exists, but it cannot exist without it.


  • 0
    J

    Then how do you know 11111 does not come from “eleven thousands one hundred and eleven 1s”. Why there must be “one 1”? 11 comes from “one 1”, so why can't 11111 come from “eleven thousands one hundred and eleven 1s”? I think you had made this proposition too early.


  • 0
    J

    And another question:

    1 1 1 1 -> 41

    The 1111 is read one 1, one 1 (or 11), which translates to 21, not 1111. This contradicts the assumption that there is a way to get 1111, and so prevents 4 or greater from appearing. Therefore, 1s cannot reach 4.

    …2132211112… also contains 1111. How can you say it is read “one 1 one 1”? You just don't have enough explanation yet. (It's easy to explain if there are no n>4 consecutive digits.)


  • 0
    M

    …2132211112… is another way of writing 4 ones in a row, and I hadn't thought of it.

    So, let me rephrase:

    To have exactly 4 ones in a row, the possible patterns are x1-11-1y and 11-11. In the first case, it would have been translated as (x+1)1-1y, while the second would be translated as 41, not 11-11.

    With n>4 consecutive 1s, in the previous step (the one which generates the current pattern), the pattern must include at least 11-11, since either x1 or 1y must be 11 for a length of 5+ 1s. If this pattern works here, then it would have worked in a 4-length chain.

    With more than 3 of a digit in a row, it can only begin an-nn-n... or nn-nn-.... If it begins an-nn, then the previous step violates the rules, as it would have translated as (a+n)n. If it begins nn-nn, the previous step would have translated to (2n)n.

    Finally, in the case where the value is an, where a = nnn (such as 111 1s), stepping back 2 steps instead brings the problem back to the problem with n>4 consecutive ones. It requires at least 11-11 to exist as a valid pattern, which, as before, would have collapsed before reaching 111 1s in a row.


  • 0
    J

    Emmm…It's ok. Can you explain your first proposition that I mentioned before?

    In order for a number greater than 4 to be created, there must be a series of numbers n>4 in length all the same digit. Therefore, there is a subset of that series where the count would only reach 4. (I call such subsets standalone subsets.)

    You said “…11111…” can only come from “one 1 one 1 one x” (1 1 x) and “x 1s one 1 one 1” (…111 1 1). These sources are impossible, right? “1 1 x” translates to “211x”. “…111 1 1” translates to “(x+2)1”. Where is the standalone subset 1111?

    The possible sources should be “m 1s n Ns” (…1111 NNNN…) where N≠1,m≥0,n≥0,m+n>0. e.g. “1111 1s”, “21111 1s”, “11111 7s”, “111112 7s”. Even if there is a subset 1111 you can not say it must be translated to 41. You just know there will be a subset, but didn't prove it may be a standalone subset to reach 4.


  • 0
    C

    nice proof
    12 characters.....


  • 0

    This seems to be a better proof link text


  • 1
    J

    I have a simpler proof.

    look the graph first,
    1
    11
    2 1
    1 2 11
    111 22 1
    3 1 22 11
    1 3 11 222 1
    111 3 2 1 3 2 11
    3 11 3 1 2 111 3 1 22 1
    1 3 2 11 3 111 2 3 11 3 11 22 11

    1 => 11
    2 => 1 and 2
    3 => 1 and 3
    So, single 1 or 2 or 3 or 4(if exists) can never produce bigger number than itself. This is TRANSFORM A.

    The only way to get bigger number is merging multiple continuous same numbers into one.

    11 => 2 and 1
    111 => 3 and 1
    22 => 2 and 2
    222 => 3 and 2
    ...
    This is TRANSFORM B.

    TRANSFORM A + TRANSFROM A, at best, we can get three 1s in a row. 1 2 => 11 12.

    TRANSFROM B + TRANSFORM B, at best, we can get two legal numbers in a row. 222 33 => 32 23.

    TRANSFROM A + TRANSFROM B, at best, we can get two legal numbers in a row. 2 11 => 12 21.

    TRANSFROM B + TRANSFROM A, 111 2 => 31 12.

    Since we only care multiple continuous same numbers, it is safe to generalize A + B cases shown above to A + B + C ... infinite case.

    We can never produce 3 same numbers in a row.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.