The task:
You have some set of tickets. First ticket is numbered M, last - N. M and N have the following limitations: 10,000,000 ≤ M <N ≤ 99999999. We say that the ticket is "lucky", if the sum is the first 4 digits.

(approx. edits) Translation:

You have some set of tickets. The first ticket has the number M, the last - N.
M and N are within: 10,000,000 ≤ M <N ≤ 99999999.
Your task: to find the number of lucky tickets in a given range.
That ticket is called lucky, the sum of the first 4 digits of which is equal to the sum of the last 4 digits.

Input:
Contains the number of the tickets.

At the entrance you have the first and last ticket number (range).

Output:
Total number of "lucky" tickets in given range.

Print the total number of lucky tickets in the given range.

#include <iostream> using namespace std; int lucky(int *a, int *b) { int count = 0, temp, i, res1 = 0, res2 = 0; int var1 = *a; for (i = 0;i < 4;i++) { temp = var1 % 10; var1 /= 10; res1 += temp; } for (i = 0;i < 4;i++) { temp = var1 % 10; var1 /= 10; res2 += temp; } if (res1 == res2) { count++; } return count; } int main() { int a, b; int *aP, *bP; aP = &a; bP = &b; int count2=0,count3=0; cin >> a >> b; for(int i = a;i<=b;i++) { if(lucky(&a,&b)>count2) { count3++; } a++; } cout << count3 << endl; system("pause"); return 0; }

I would like to reduce the execution time from 8 seconds to at least 3, with input data 10000000 and 99999999 .

2 answers 2

In a cycle that increases the number 1 at a time, the sum of the digits of the upper four digits changes once every 10,000 cycles, and this happens when the lower 4 digits are 0.

There is no need to decompose the number into 4 digits each time, for these are 4 division operations. You can make a small array with sums of digits of two digits (if there is a lot of memory, you can calculate sums for all 4 digits in advance).

Based on this, we prepare in advance an array of sums for numbers from 0 to 99 and use it to calculate the total sum of 4 digits, splitting in half by 2 digits. The sum for the highest part of the number is calculated only in the case when it has changed.

 #include <iostream> using namespace std; int main() { int a, b; int count3=0; a = 10000000; b = 99999999; char sum[100]; for(int i=0;i<=99;i++) sum[i]=i/10+i%10; //cin >> a >> b; int h=0,h_sum; for(int i = a;i<=b;i++) { int l=i%10000; if(l==0 || h==0) { h=i/10000; h_sum=*(sum+h/100)+*(sum+h%100); } count3+= (sum[l/100]+sum[l%100] == h_sum); } cout << count3 << endl; return 0; }

To demonstrate the work with "pointers" I replaced the square brackets in one place when referring to sum for a pointer calculation. Further reduction to the "training" mind, I leave to you. Mass options: prepare the sum array as a separate function, make the calculation of the sum of digits into a separate function and transfer to it, in addition to the number, a pointer to this array. In addition, the function must somewhere store the previous calculated value of h_sum, it can also be passed by pointer ...

    Let's just say, there are 2 options for acceleration - rewrite everything with 0 and the correct algorithm based on the dynamics of the number. And 2 - just write what is normal. Why a bunch of pointers, why strange checks ... For example, this code has a chance to work in 3 seconds. On the pinch, you can deploy cycles.

     int main() { int a, b; int count3=0; a = 10000000; b = 99999999; //cin >> a >> b; for(int i = a;i<=b;i++) { int ii = i; int z = 0; int x = 0; for (int q = 0; q < 4; q++,ii/=10) z+=ii%10; for (int q = 0; q < 4; q++,ii/=10) x+=ii%10; count3+= (z == x); } cout << count3 << endl; return 0; }
    • Thanks for the answer, just asking for the use of pointers in the task. contester.iitu.kz:9006/ru/… (Russian version of the site) - Kairat Amanzharov
    • @KairatAmanzharov they are not needed here, only slow down the work. - pavel
    • We have the Pointers topic, and in all the assignments they are asked to use them, and we must write everything in the function - Kairat Amanzharov
    • Well, then think for yourself, somehow uncivilized from the current competition of the task to do everything - pavel