9 weeks ago

John 910

Hyderabad

Question 1

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 - bill0, bill1,..... ,billN-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<= billi <= 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.

Question 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.

8 months ago

Akshay Sharma 990

Chandigarh

Q1 Solution

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).

2.2 years ago

Dolton Fernandes 30

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 ++;