Home » Technical Interview Questions » Algorithm Interview Questions » Special Number

Special Number


Reading Time - 2 mins

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)
                    store.add(arr.get(j));
            }
        }
        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[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}

Complexity Analysis

Time Complexity=O(n^2)

READ  Sieve of Eratosthenes

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.

Special Number
Special number explained

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++) 
        { 
            store.add(arr.get(i)); 
            max = Math.max(max,arr.get(i)); 
        }
        LinkedHashSet<Integer>ans=new LinkedHashSet<Integer>();
        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))
                        ans.add(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[0]); 
  
    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

READ  Flood Fill LeetCode

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions