DynamoDB table structure - sort by numeric field without any hash key

Question

I have a bunch (edit: 2.5 million) of puzzles that I would like to store and query in DynamoDB.

The relevant structure of each puzzle is as follows:

ID	Difficulty	OtherString	...
ab	1500	foo1	...
x0	1645	foo2	...
c2	1645	foo3	...
d5	1431	foo4	...
oz	1500	foo5	...

Each ID is a unique string. Each Difficulty is a numeric value, more or less in the range of 0-3000. There are other fields too but not interesting for this question.

In terms of access patterns, I need to:

1. Update these values from time to time by the ID.
2. Get a random puzzle within a given range, e.g. 1500 +/- 50.

I imagine the ID is best as the HASH KEY but do not believe I can have the Difficulty field as the SORT KEY as there can be duplicate values. There is nothing else required to partition the data, so no need for any other type of composite key, imo.

Should I just have the ID as the HASH KEY and do a scan operation to get a random puzzle, filtering by the Difficulty? Is this possible? is there a better way to model this data? I would imagine having the Difficulty in the SORT KEY (somehow) would help speed up searches and use less resources to do so.

Many thanks