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