Count numbers where three first digits equal last

2020-08-09 07:40发布

问题:

How do I efficiently count the zero padded six digit numbers where the first three digits equal the last three?

My solution is like this. But this is not efficient solution. I have to find best way

public class TicketNumber { 
  public static void main(String[] args) { 
   int i1, i2, i3, i4, i5, i6, count = 0; 
   String str=""; 
   for (i1 = 0; i1 <= 9; i1++) { 
      for (i2 = 0; i2 <= 9; i2++) { 
         for (i3 = 0; i3 <= 9; i3++) { 
            for (i4 = 0; i4 <= 9; i4++) { 
               for (i5 = 0; i5 <= 9; i5++) { 
                  for (i6 = 0; i6 <= 9; i6++) { 
                     if ((i1+i2+i3) == (i4+i5+i6)) { 
                        count++; 
                     }
                  }
               }
            }
         }
      }
   }
   System.out.println(count);
  }
}

I should print all numbers between 000000-999999 which compatible with i1+i2+i3 = i4+i5+i6 condition

回答1:

To count all the values where the first three digits equals the last three digits. (As you solution suggests)

You can calculate the range for i4, i5 and the value i6 which makes this much faster.

int count = 0;
for (int i1 = 0; i1 <= 9; i1++) {
    for (int i2 = 0; i2 <= 9; i2++) {
        for (int i3 = 0; i3 <= 9; i3++) {
            int sum = i1 + i2 + i3;
            for (int i4 = Math.max(0, sum - 18); i4 <= Math.min(9, sum); i4++) {
                int min5 = Math.max(0, sum - i4 - 9);
                int max5 = Math.min(9, sum - i4);
                if (min5 <= max5) // one solution for i6 each
                    count += max5 - min5 + 1;
            }
        }
    }
}
System.out.println(count);

prints the same answer as your solution;

55252

This is a further optimisation, it recognises that the order of the first three digits doesn't matter.

int count = 0;
for (int i1 = 0; i1 <= 9; i1++) {
    for (int i2 = 0; i2 <= i1; i2++) {
        for (int i3 = 0; i3 <= i2; i3++) {
            int different = ((i1 != i2)?1:0) + ((i1 != i3)?1:0) + ((i2 != i3)?1:0);
            int combinations = different == 0 ? 1 : different == 2 ? 3 : 6;
            int sum = i1 + i2 + i3;
            for (int i4 = Math.max(0, sum - 18); i4 <= Math.min(9, sum); i4++) {
                int min5 = Math.max(0, sum - i4 - 9);
                int max5 = Math.min(9, sum - i4);
                if (min5 <= max5) // one solution each
                    count += combinations * (max5 - min5 + 1);
            }
        }
    }
}
System.out.println(count);

What this does is say 123 or 132 or 213 or 231 or 312 or 321 have the same number of solutions. 111 has a factor of 1, 112 has a factor of 3 and 123 has a factor of 6.