How to solve the problem of lucky tickets?

Question

Programming

There is a tape of tickets with eight-digit numbers. The first ticket has the number M, the last - N. The values ​​M and N correspond to the following relationship: 10000000 ≤ M < N ≤ 99999999. It is necessary to determine the number of "lucky" tickets in the tape. A ticket is considered "lucky" if the sum of the first four digits is equal to the sum of the last four digits.
Help with drawing up an algorithm.
Smog only for all possible cases, excluding M and N:

int C[37];
  int T, Count = 0;
  for (T = 0; T < 37; ++T)
    C[T] = 0;

  
  for (int a1 = 0; a1 <= 9; ++a1)
    for (int a2 = 0; a2 <= 9; ++a2)
      for (int a3 = 0; a3 <= 9; ++a3) {
        for (int a4 = 0; a4 <= 9; ++a4) {
          T = a1 + a2 + a3 + a4;
          C[T]++;
        }
      }
  
  for (T = 0; T < 37; ++T) {
    //printf("%d\n", C[T]);
    Count += (C[T] * C[T]);
  }

  printf("%d\n", Count);

Answer 1

Something like this:

int S0[37],S1[37],S2[37],S3[37],S4[37];

void Expand(int *a,int *b,int n){
  int s0=0;
  for(int i=0;i<n+10;i++){
    if(i<n) s0+=a[i];
    if(i>=10) s0-=a[i-10];
    b[i]=s0;
  }
}

int Conv(int *S,int balance,int m){
  int res=0;
  while(--m>=0) res+=S[m]*S4[balance+m];
  return res;
}

// number of tickets in 0..u-1
int NHappy(int u){
  int res=0;
  int balance=0;
  int digit;

  digit=u/10000000; u%=10000000;
  for(int i=0;i<digit;i++) res+=Conv(S3,balance++,28);
  digit=u/1000000; u%=1000000;
  for(int i=0;i<digit;i++) res+=Conv(S2,balance++,19);
  digit=u/100000; u%=100000;
  for(int i=0;i<digit;i++) res+=Conv(S1,balance++,10);
  digit=u/10000; u%=10000;
  for(int i=0;i<digit;i++) res+=S4[balance++];
  digit=u/1000; u%=1000;
  for(int i=0;i<digit && balance>=0;i++) res+=S3[balance--];
  digit=u/100; u%=100;
  for(int i=0;i<digit && balance>=0;i++) res+=S2[balance--];
  digit=u/10; u%=10;
  for(int i=0;i<digit && balance>=0;i++) res+=S1[balance--];
  if(balance>=0 && balance<u) res++;
  return res;
}

void __cdecl main(){
  S0[0]=1;
  Expand(S0,S1,10);
  Expand(S1,S2,19);
  Expand(S2,S3,28);
  Expand(S3,S4,37);

  int m,n;
  for(;;){
    printf("m,n: ");
    scanf("%d%d",&m,&n);
    printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
  }
}

No input validation is done. On simple tests, the results were correct. Works, according to my estimates, faster than 2000 operations. If you need to check many ranges, then you can pre-calculate the partial sums of Conv () in loops, and then any range will be calculated in two dozen operations (and will not require a gigabyte of memory).
UPD: Here is an optimized version:

int S[8][38];

void InitS(){
  for(int i=1;i<38;i++) S[0][i]=1;
  for(int a=1;a<9;a++){
    int s0=0;
    for(int i=1;i<=37;i++){
      s0+=S[a-1][i];
      if(i>10) s0-=S[a-1][i-10];
      S[a][i]=s0;
    }
  }
}

// number of tickets in 0..u-1
int NHappy(int u){
  int res=0;
  int balance=36;
  for(int a=7,b=10000000;a>=0;a--,b/=10){
    int digit=u/b;
    u%=b;
    int b1;
    if(a>3){
      balance-=9;
      res+=S[a][b1=balance+digit]-S[a][balance];
    } else{
      b1=balance-digit; if(b1<0) b1=-1;
      res+=S[a][balance+1]-S[a][b1+1];
    }
    balance=b1;
  }
  return res;
}

void __cdecl main(){
  InitS();
  int m,n;
  for(;;){
    printf("m,n: ");
    scanf("%d%d",&m,&n);
    printf("Result: %d\n",NHappy(99999999)+1-NHappy(m)-NHappy(99999999-n));
  }
}

Don't ask why :)

Answer 2

Here is a solution in php, I'm not very strong in C ++, but I think you can split the string into elements and convert them to arrays. I also think that my code is clear, the syntax of php is not much different from sish. In general, you will be fine.

<?php

$lucky = 0;
for ($i = 10000000; $i < 99999999; $i++) {
  $str = (string) $i;
    $sum1 = (int) $str[0] + (int) $str[1] + (int) $str[2] + (int) $str[3];
    $sum2 = (int) $str[4] + (int) $str[5] + (int) $str[6] + (int) $str[7];
    if ($sum1 == $sum2) {
    	$lucky++;
    }
}

echo $lucky;

UPD: I tested the code, this one seems to work.
Parentheses before variables are type conversions.

Answer 3

I think, to solve this problem something like this:
Let's say
M = AAAA BBBB N =
CCCC
DDDD number of lucky tickets from (AAAA+1) 0000 to (CCCC-1) 9999 - that is, an array of sums from AAAA+1 to CCCC-1 and elementwise multiply it by the array C from the first step, finally getting the sum. 4. We count the number of lucky tickets from CCCC 0000 to CCCC DDDD. 5. We sum up all three quantities in steps 2-4, and the problem is solved. The complexity of each subproblem is the same as that of the original problem. I think I've outlined the algorithm clearly.
UPD: Well, take into account the extreme case, if the first 4 digits of M and N are the same - then all this does not need to be counted, but only 1 search from the right 4 digits of the first number to the right four digits of the second, and check their sum of digits for equality to the left sum of digits .

Answer 4

Change task.
1. Format AAAABBBB - a lucky ticket if:
the sum of the digits of the AAAA=BBBB parts,
if the left and right parts are equal with any order of digits.
Max. number of lucky tickets - 9000.
2. If M < N, then the number of tickets<=9000.
3. Range: tickets count=((NM)/10000)%10000