Searching: Find the value and its double in the array

Problem Statement:

You are given an unsorted array and element k.

You need to find the double the value of k and return the value of k

Example:

Input : arr[] = { 2, 3, 4, 5, 8, 10, 1, 6 }, k = 2
Output: 16

K = 2, found in the array, double is 4 and we search for it.
K = 4, found in the array, double is 16 and we search for it.
K = 16, is NOT in the array, hence result is 16

Solution 1: Brute force approach

Traverse each element and check if a[i] == k then k = 2 * k

Then repeat the process

Then repeat the last value of k

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Sort and search

Sort the array

Then search the element and check if K*2 after the array.

Time Complexity: O(n logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

int solution_1 (int a[], int n, int k) 
{ 

	bool exist = true; 
	
	while(exist)
	{ 
		
		exist = false; 
		
		for (int i = 0; i < n; i++) 
		{ 
			
			if (a[i] == k)
			{ 
				k *= 2; 
				exist = true; 
				break; 
			} 
		} 
		
	} 

	return k; 
} 

int solution_2(int a[], int n, int k) 
{ 
  
    sort(a, a + n); 
  
    for (int i = 0; i < n; i++) 
    { 
          
        if (a[i] == k) 
            k *= 2; 
    } 
  
    return k; 
} 

int main() 
{ 
	int arr[] = { 2, 3, 4, 5, 8, 10, 1, 6 }, k = 2; 

	int n = sizeof(arr) / sizeof(arr[0]); 
	
	cout << solution_1(arr, n, k)<<endl; 
	cout << solution_2(arr, n, k); 
	
	return 0; 
} 

Output

16
16