Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider,

F4(y) = the number of digits 4 in decimal representation of the positive integer y

and

F7(y)=the number of digits '7' in decimal representation of the positive integer y.

For the given positive integer N ,Find the total number of different pairs (L, R)

such that F4(L) + F4(L + 1) + ... + F4(R) equals to F7(L) + F7(L + 1) + ... + F7(R)

and 1 ≤ L ≤ R ≤ N.

Examples::

N=1 Ans::1

N=2 Ans::3

N=3 Ans::6

N=4 Ans::6

N=5 Ans::7

N=6 Ans::9

N=7 Ans::13

N=8 Ans::18

N=9 Ans::24

N=10 Ans::31

N=11 Ans::39

N=12 Ans::48

N=13 Ans::58

N=14 Ans::61

N=15 Ans::65

N=16 Ans::70

N=17 Ans::81

N=18 Ans::93

N=19 Ans::106

N=20 Ans::120

How to solve this problem Efficiently??

share|improve this question
    
This is a classic dynamic programming program,i think..Think in terms of 4 and 7 and formulate DP –  user24478 Feb 6 '12 at 15:23
add comment

2 Answers

up vote 1 down vote accepted

Here's some Java code that calculates this, based on the observation that for each $N$ the change relative to $N-1$ is due only to the cases where $R=N$. This takes time quadratic in $N$; I suspect you could make it linear in $N$ by making use of the regularities, but I'm not going to put any effort into that unless you say something about the motivation for this question :-).

public class FourSeven {
    static int count (char [] c,char d) {
        int count = 0;
        for (char a : c)
            if (a == d)
                count++;
        return count;
    }

    public static void main (String [] args) {
        int count = 0;
        for (int n = 1;;n++) {
            int diff = 0;
            for (int l = n;l > 0;l--) {
                char [] c = String.valueOf (l).toCharArray ();
                diff += count (c,'4') - count (c,'7');
                if (diff == 0)
                    count++;
            }
            System.out.println (n + " : " + count);
        }
    }
}
share|improve this answer
add comment

It can be done linear time using Dynamic programming... Use the concept,Dp[i]=DP[i-1]+{Number of new/valid pairs that is not seen in i-1 } ie.Dp[i]=DP[i-1]+{Number of new/valid pairs among{(1,i),(2,i),(3,i)....(i,i)} }.. But the challenging task is to calculate Number of new/valid pairs that is not seen in i-1 .

fOR THAT we have to become more mathematical,i guess..Think in terms of Number of 4's and 7's seen so far... Only dynamic programming can ensure the liner O(n) solutions..

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.