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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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


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.


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|cite|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
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)
        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)
            System.out.println (n + " : " + count);
share|cite|improve this answer

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|cite|improve this answer

Your Answer


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.