0
$\begingroup$

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??

  • 0
    This is a classic dynamic programming program,i think..Think in terms of 4 and 7 and formulate DP2012-02-06

2 Answers 2

1

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);
        }
    }
}
1

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..