# Special Number

Difficulty Level Easy
Frequently asked in Jio MAQ o9 solutions TCS
Number-Digits School ProgrammingViews 1794

What can be so special about a number?

Let us find out.

We have with us an array of N numbers. A number can be special if it is divisible by one or more numbers except for the number itself.

Firstly let us clear this with a few examples before we jump into anything else

Array of 1,2,3

Special numbers 2 and 3

Why?

2 is divisible by 1 as well 3

The array of 1,2,5,9

Special numbers will be 2,5 and 9

Why?

As these numbers are divisible by 1

An array of 2,3,4,6,8,9

Special numbers will be 4.6.8.9

Secondly, let us look at how to approach this problem

## Approach 1 for Special Number

### Brute Force

• We traverse through the array
• We check the elements that divide each element

### Java Code For Special Numbers

```// "static void main" must be defined in a public class.
public class Main
{
public static void diCheck(List<Integer> arr, int n)
{
Set<Integer> store = new HashSet<Integer>();
for(int i=0;i<arr.size();i++)
{
for(int j=i+1;j<arr.size();j++)
{
if(arr.get(j)%arr.get(i)==0)
}
}
for(Integer a:store)
{
System.out.print(a+" ");
}
}
public static void main(String[] args)
{
List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5);
int n = arr.size();
diCheck(arr, n);
}
}```

### C++ Code For Special Numbers

```void diCheck(int arr[], int n)
{
unordered_set<int> store;
int maxs = -1;
for (int i = 0; i < n; i++)
{
for(int j=i+1;j<n;j++)
{
if(arr[j]%arr[i]==0)
store.insert(arr[j]);
}
}
for (auto x : store)
cout << x << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 };
int n = sizeof(arr) / sizeof(arr);

diCheck(arr, n);

return 0;
}```

### Complexity Analysis

Time Complexity=O(n^2)

How?

• The above approach uses two loops
• Firstly, an outer one to go over the divisor
• Secondly. inner one to go over the dividend
• This brings the time complexity to O(n^2)

Space Complexity=O(1)

How?

We use only a variable thus we do not need much space

## Approach 2 for Special Number

### Using a hash table

Firstly, let us break down the approach into small bite-sized palatable pieces.

• Firstly sort all the elements
• Find the max element using a variable
• Need of the max element?
• To use it to find the available divisors up to that number
• We start from num*2
• We add the number to itself to get the multiples
• Every time we get a multiple we store it into a set
• We store the numbers into sets to ensure that none of the numbers we obtain is duplicate
• If there is a divisor then the number is special
• The special number is thus added

Secondly, let me get a small image to run through the entire process. This would ensure that everyone who could not get a grip on the problem understands it fully.

The red places here suggest that the numbers have already been added to the map.

### Java Code

```// "static void main" must be defined in a public class.
public class Main
{
public static void diCheck(List<Integer> arr, int n)
{
List<Integer> store = new ArrayList<Integer>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
max = Math.max(max,arr.get(i));
}
for(int i=0;i<n;i++)
{
if(arr.get(i)!=0)
{
for(int j=arr.get(i)*2;j<max;j++)
{
if(store.contains(j))
}
}
}
List<Integer>ret=new ArrayList<Integer>(ans);
for(int i=0;i<ret.size();i++)
System.out.print(ret.get(i)+" ");
}
public static void main(String[] args)
{
List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5);
int n = arr.size();
diCheck(arr, n);
}
}```

### C++ Code

```void diCheck(int arr[], int n)
{
unordered_set<int> store;
int maxs = -1;
for (int i = 0; i < n; i++)
{
store.insert(arr[i]);
//Finding the max element
maxs= max(maxs, arr[i]);
}

// Traversing the array elements and storing the multiples
unordered_set<int> res;
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
{
for (int j = arr[i] * 2; j <= maxs; j++)
{
if (store.find(j) != store.end())
res.insert(j);
}
}
}
unordered_map<int, int> map;
for(int i = 0; i < n; i++)
map[arr[i]]=map[arr[i]]+1;

unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = map.begin(); it != map.end(); it++)
{
if (it->second >= 2)
{
if (res.find(it->first) == res.end())
{
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}

// If frequency is greater than 1 and is divisible by any other number
if (res.find(it->first) != res.end())
{
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
//Printing special numbers
for (auto x : ans)
cout << x << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 };
int n = sizeof(arr) / sizeof(arr);

diCheck(arr, n);

return 0;
}```
`1, 2, 3, 5, 8, 6, 9, 10`
`2,3,5,8,9,10`

Note: The above approach works well only for small numbers

### Complexity Analysis For Special Number

Time Complexity=O(n^2)

• The time complexity for the approach sums up to O(n^2)
• The sorting takes O(n log n) time
• We go over the outer loop and select a number from the hash
• In the inner loop, we look for the divisors and add them to the set if they are present
• Eventually summing up the time complexity to O(nlogn)+O(n^2)
• As n^2>n logn
• The time complexity becomes O(n^2)

Space Complexity=O(n)

• We use a hash and a set to keep track of the elements.
• We have an array/ArrayList/vector of size n provided.
• Thus space taken in storing all the elements sums up to O(n).

References

Translate »