128. Lucky tickets

Count the number of lucky tickets for which the sum of the first three digits is equal to n.

A lucky ticket is a six-digit ticket in which the sum of the first three digits is equal to the sum of the last three digits.

Input. One positive integer n (n ≤ 27).

Output. Print the number of lucky tickets.

Sample input	Sample output
1	9

SOLUTION

full search

Algorithm analysis

Compute the number p of three-digit numbers (which may start with zero) whose digits sum to n. If we append any three-digit number with digit sum n to another three-digit number with the same digit sum, we obtain a lucky ticket. Therefore, the number of lucky tickets is equal to p².

Example

Consider the case when n = 1. The three-digit numbers whose digits sum to 1 are 001, 010, and 100. By concatenating any one of them with any other, we obtain 9 lucky tickets.

Algorithm implementation

Read the input value of n.

scanf("%d",&n);

The variable p stores the number of three-digit numbers whose digits sum to n.

p = 0;

Iterate over the digits of the three-digit number . If the sum of its digits is equal to n, increment the value of p by 1.

for(i = 0; i <= 9; i++)

for(j = 0; j <= 9; j++)

for(k = 0; k <= 9; k++)

if (i + j + k == n) p++;

Compute and print the answer.

res = p * p;

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

Java implementation

import java.util.*;

public class Main

{

public static void main(String args[])

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int p = 0;

for(int i = 0; i <= 9; i++)

for(int j = 0; j <= 9; j++)

for(int k = 0; k <= 9; k++)

if (i + j + k == n) p++;

int res = p * p;

System.out.println(res);

con.close();

}

}

Python implementation

Read the value of n.

n = int(input())

The variable p stores the number of three-digit numbers whose digits sum to n.

p = 0

Iterate over the digits of the three-digit number . If the sum of its digits is equal to n, increment the value of p by 1.

for i in range(10):

for j in range(10):

for k in range(10):

if (i + j + k == n): p += 1

Compute and print the answer.

res = p * p;

print(res)