Entering edit mode

Click here to Practice

Submit Problem to OJ

A company is planning a big sale at which they will give their customers a special promotional discount. Each customer that purchases a product from the company has a unique customerID numbered from 0 to N-1. Andy, the marketing head of the company, has selected bill amounts of the N customers for the promotional scheme. The discount will be given to the customers whose bill amounts are perfect squares. The customers may use this discount on a future purchase.

Write an algorithm to help Andy find the number of customers that will be given discounts.

**Input**

The first line of the input consists of an integer *numOfCust*, representing the number of customers whose bills are selected for the promotional discount (N).

The second line consists of N space-separated integers - bill*0*, bill*1*,..... ,bill*N-1*, representing the bill amounts of the N customers selected for the promotional discount.

**Output**

Print an integer representing the number of customers that will be given discounts.

**Constraints**

0 <= *numOfCust* <= 10^6

0<= bill*i* <= 10^6

0 <= i < *numOfCust*

**Example**

```
Input:
6
25 77 54 81 48 34
Output:
2
```

**Explanation:**

The bill amounts that are perfect squares are 25 and 81. So, the output is 2.

A company is transmitting data to another server. The data is in the form of numbers. To secure the data during transmission, they plan to obtain a security key that will be sent along with the data. The security key is identified as the count of the unique repeating digits in the data.

Write an algorithm to find the security key for the data.

**Input**

The input consists of an integer- *data*, representing the data to be transmitted

**Output**

Print an integer representing the security key for the given data

**Example**

```
Input:
578378923
Output:
3
```

**Explanation**

The repeated digits in the data are 7 Band So, the security key is 3.

Entering edit mode

**Understanding the question**

- We are given an array of sizes N, where each A[i] represent the bill amount of ith customer
- we are asked to find the number of customers that are actually going to receive the discount.
- Reading question carefully we easily get to know that all the customers are going to receive the discount whose bill value is a perfect square for example 1,4,9,16,25,36.

**Breakdown of question in one line**

- Count the number of perfect square in a given array

**Approach/Detailed Solution**

one optimal approach that we can use is to choose an element and check if it is a perfect square or not (that can be done in sqrt(N)) easily, if yes we increase the count else don't change the count, Time Complexity: O(N*sqrt(N)).

bool check(int x) {

`if (ceil((double)sqrt(n)) == floor((double)sqrt(n))) { return 1; } return 0;`

}

-Above is the snippet to check if a number is a perfect square or not in the best time complexity that is sqrt(Number).

Entering edit mode

Since we know that there can be at max 10 different digits (0 to 9), we can just maintain a count array to store the count of digits in the stream. Then we need to just find the number of digits in the count array that have a frequency of atleast 2.

**Code:**

```
int count[10]={0};
for (auto v:s) count[v-'0'] ++; // s is the input string
int ans=0;
for(int i=0;i<10;i++) if(count[i] > 1) ans ++;
```